Thursday Nov 17, 2011

How John Got 15x Improvement Without Really Trying

The following article was published on a Sun Microsystems website a number of years ago by John Feo. It is still useful and worth preserving. So I'm republishing it here. 

How I Got 15x Improvement Without Really Trying

John Feo, Sun Microsystems

Taking ten "personal" program codes used in scientific and engineering research, the author was able to get from 2 to 15 times performance improvement easily by applying some simple general optimization techniques.

Introduction

Scientific research based on computer simulation depends on the simulation for advancement. The research can advance only as fast as the computational codes can execute. The codes' efficiency determines both the rate and quality of results. In the same amount of time, a faster program can generate more results and can carry out a more detailed simulation of physical phenomena than a slower program. Highly optimized programs help science advance quickly and insure that monies supporting scientific research are used as effectively as possible.

Scientific computer codes divide into three broad categories: ISV, community, and personal. ISV codes are large, mature production codes developed and sold commercially. The codes improve slowly over time both in methods and capabilities, and they are well tuned for most vendor platforms. Since the codes are mature and complex, there are few opportunities to improve their performance solely through code optimization. Improvements of 10% to 15% are typical. Examples of ISV codes are DYNA3D, Gaussian, and Nastran.

Community codes are non-commercial production codes used by a particular research field. Generally, they are developed and distributed by a single academic or research institution with assistance from the community. Most users just run the codes, but some develop new methods and extensions that feed back into the general release. The codes are available on most vendor platforms. Since these codes are younger than ISV codes, there are more opportunities to optimize the source code. Improvements of 50% are not unusual. Examples of community codes are AMBER, CHARM, BLAST, and FASTA.

Personal codes are those written by single users or small research groups for their own use. These codes are not distributed, but may be passed from professor-to-student or student-to-student over several years. They form the primordial ocean of applications from which community and ISV codes emerge. Government research grants pay for the development of most personal codes. This paper reports on the nature and performance of this class of codes.

Over the last year, I have looked at over two dozen personal codes from more than a dozen research institutions. The codes cover a variety of scientific fields, including astronomy, atmospheric sciences, bioinformatics, biology, chemistry, geology, and physics. The sources range from a few hundred lines to more than ten thousand lines, and are written in Fortran, Fortran 90, C, and C++. For the most part, the codes are modular, documented, and written in a clear, straightforward manner. They do not use complex language features, advanced data structures, programming tricks, or libraries. I had little trouble understanding what the codes did or how data structures were used. Most came with a makefile.

Surprisingly, only one of the applications is parallel. All developers have access to parallel machines, so availability is not an issue. Several tried to parallelize their applications, but stopped after encountering difficulties. Lack of education and a perception that parallelism is difficult prevented most from trying. I parallelized several of the codes using OpenMP, and did not judge any of the codes as difficult to parallelize.

Even more surprising than the lack of parallelism is the inefficiency of the codes. I was able to get large improvements in performance in a matter of a few days applying simple optimization techniques. Table 1 lists ten representative codes [names and affiliation are omitted to preserve anonymity]. Improvements on one processor range from 2x to 15.5x with a simple average of 4.75x. I did not use sophisticated performance tools or drill deep into the program's execution character as one would do when tuning ISV or community codes. Using only a profiler and source line timers, I identified inefficient sections of code and improved their performance by inspection. The changes were at a high level. I am sure there is another factor of 2 or 3 in each code, and more if the codes are parallelized. The study’s results show that personal scientific codes are running many times slower than they should and that the problem is pervasive.

Computational scientists are not sloppy programmers; however, few are trained in the art of computer programming or code optimization. I found that most have a working knowledge of some programming language and standard software engineering practices; but they do not know, or think about, how to make their programs run faster. They simply do not know the standard techniques used to make codes run faster. In fact, they do not even perceive that such techniques exist. The case studies described in this paper show that applying simple, well known techniques can significantly increase the performance of personal codes. It is important that the scientific community and the Government agencies that support scientific research find ways to better educate academic scientific programmers. The inefficiency of their codes is so bad that it is retarding both the quality and progress of scientific research.

#

cache
performance

redundant
operations

loop
structures

performance
improvement

1

x

x


15.5

2

x



2.8

3

x

x


2.5

4


x


2.1

5

x

x


2.0

6


x


5.0

7

x



5.8

8


x


6.3

9




2.2

10

x


x

3.3

Table 1 — Area of improvement and performance gains of 10 codes

The remainder of the paper is organized as follows: sections 2, 3, and 4 discuss the three most common sources of inefficiencies in the codes studied. These are cache performance, redundant operations, and loop structures. Each section includes several examples. The last section summaries the work and suggests a possible solution to the issues raised.

Optimizing cache performance

Commodity microprocessor systems use caches to increase memory bandwidth and reduce memory latencies. Typical latencies from processor to L1, L2, local, and remote memory are 3, 10, 50, and 200 cycles, respectively. Moreover, bandwidth falls off dramatically as memory distances increase. Programs that do not use cache effectively run many times slower than programs that do.

When optimizing for cache, the biggest performance gains are achieved by accessing data in cache order and reusing data to amortize the overhead of cache misses. Secondary considerations are prefetching, associativity, and replacement; however, the understanding and analysis required to optimize for the latter are probably beyond the capabilities of the non-expert. Much can be gained simply by accessing data in the correct order and maximizing data reuse. 6 out of the 10 codes studied here benefited from such high level optimizations.

Array Accesses

The most important cache optimization is the most basic: accessing Fortran array elements in column order and C array elements in row order. Four of the ten codes—1, 2, 4, and 10—got it wrong. Compilers will restructure nested loops to optimize cache performance, but may not do so if the loop structure is too complex, or the loop body includes conditionals, complex addressing, or function calls. In code 1, the compiler failed to invert a key loop because of complex addressing

      do I = 0, 1010, delta_x
        IM = I - delta_x
        IP = I + delta_x
        do J = 5, 995, delta_x
          JM = J - delta_x
          JP = J + delta_x
          T1 = CA1(IP, J) + CA1(I, JP)
          T2 = CA1(IM, J) + CA1(I, JM)
          S1 = T1 + T2 - 4 * CA1(I, J)
          CA(I, J) = CA1(I, J) + D * S1
        end do
      end do

In code 2, the culprit is conditionals

      do I = 1, N
        do J = 1, N
        If (IFLAG(I,J) .EQ. 0) then
          T1 = Value(I, J-1)
          T2 = Value(I-1, J)
          T3 = Value(I, J)
          T4 = Value(I+1, J)
          T5 = Value(I, J+1)
          Value(I,J) = 0.25 * (T1 + T2 + T5 + T4)
          Delta = ABS(T3 - Value(I,J))
          If (Delta .GT. MaxDelta) MaxDelta = Delta
        endif
        enddo
      enddo

I fixed both programs by inverting the loops by hand.

Code 10 has three-dimensional arrays and triply nested loops. The structure of the most computationally intensive loops is too complex to invert automatically or by hand. The only practical solution is to transpose the arrays so that the dimension accessed by the innermost loop is in cache order. The arrays can be transposed at construction or prior to entering a computationally intensive section of code. The former requires all array references to be modified, while the latter is cost effective only if the cost of the transpose is amortized over many accesses. I used the second approach to optimize code 10.

Code 5 has four-dimensional arrays and loops are nested four deep. For all of the reasons cited above the compiler is not able to restructure three key loops. Assume C arrays and let the four dimensions of the arrays be i, j, k, and l. In the original code, the index structure of the three loops is

    L1: for i   L2: for i   L3: for i
      for l       for l       for j
      for k       for j       for k
      for j       for k       for l

So only L3 accesses array elements in cache order. L1 is a very complex loop—much too complex to invert. I brought the loop into cache alignment by transposing the second and fourth dimensions of the arrays. Since the code uses a macro to compute all array indexes, I effected the transpose at construction and changed the macro appropriately. The dimensions of the new arrays are now: i, l, k, and j. L3 is a simple loop and easily inverted. L2 has a loop-carried scalar dependence in k. By promoting the scalar name that carries the dependence to an array, I was able to invert the third and fourth subloops aligning the loop with cache.

Code 5 is by far the most difficult of the four codes to optimize for array accesses; but the knowledge required to fix the problems is no more than that required for the other codes. I would judge this code at the limits of, but not beyond, the capabilities of appropriately trained computational scientists.

Array Strides

When a cache miss occurs, a line (64 bytes) rather than just one word is loaded into the cache. If data is accessed stride 1, than the cost of the miss is amortized over 8 words. Any stride other than one reduces the cost savings. Two of the ten codes studied suffered from non-unit strides. The codes represent two important classes of "strided" codes.

Code 1 employs a multi-grid algorithm to reduce time to convergence. The grids are every tenth, fifth, second, and unit element. Since time to convergence is inversely proportional to the distance between elements, coarse grids converge quickly providing good starting values for finer grids. The better starting values further reduce the time to convergence. The downside is that grids of every nth element, n > 1, introduce non-unit strides into the computation. In the original code, much of the savings of the multi-grid algorithm were lost due to this problem. I eliminated the problem by compressing (copying) coarse grids into continuous memory, and rewriting the computation as a function of the compressed grid. On convergence, I copied the final values of the compressed grid back to the original grid. The savings gained from unit stride access of the compressed grid more than paid for the cost of copying. Using compressed grids, the loop from code 1 included in the previous section becomes

      do j = 1, GZ
        do i = 1, GZ
          T1 = CA(i+0, j-1) + CA(i-1, j+0)
          T4 = CA1(i+1, j+0) + CA1(i+0, j+1)
          S1 = T1 + T4 - 4 * CA1(i+0, j+0)
          CA(i+0, j+0) = CA1(i+0, j+0) + DD * S1
        enddo
      enddo

where CA and CA1 are compressed arrays of size GZ.

Code 7 traverses a list of objects selecting objects for later processing. The labels of the selected objects are stored in an array. The selection step has unit stride, but the processing steps have irregular stride. A fix is to save the parameters of the selected objects in temporary arrays as they are selected, and pass the temporary arrays to the processing functions. The fix is practical if the same parameters are used in selection as in processing, or if processing comprises a series of distinct steps which use overlapping subsets of the parameters. Both conditions are true for code 7, so I achieved significant improvement by copying parameters to temporary arrays during selection.

Data reuse

In the previous sections, we optimized for spatial locality. It is also important to optimize for temporal locality. Once read, a datum should be used as much as possible before it is forced from cache. Loop fusion and loop unrolling are two techniques that increase temporal locality. Unfortunately, both techniques increase register pressure—as loop bodies become larger, the number of registers required to hold temporary values grows. Once register spilling occurs, any gains evaporate quickly. For multiprocessors with small register sets or small caches, the sweet spot can be very small. In the ten codes presented here, I found no opportunities for loop fusion and only two opportunities for loop unrolling (codes 1 and 3).

In code 1, unrolling the outer and inner loop one iteration increases the number of result values computed by the loop body from 1 to 4,

      do J = 1, GZ-2, 2
        do I = 1, GZ-2, 2
          T1 = CA1(i+0, j-1) + CA1(i-1, j+0)
          T2 = CA1(i+1, j-1) + CA1(i+0, j+0)
          T3 = CA1(i+0, j+0) + CA1(i-1, j+1)
          T4 = CA1(i+1, j+0) + CA1(i+0, j+1)
          T5 = CA1(i+2, j+0) + CA1(i+1, j+1)
          T6 = CA1(i+1, j+1) + CA1(i+0, j+2)
          T7 = CA1(i+2, j+1) + CA1(i+1, j+2)
          S1 = T1 + T4 - 4 * CA1(i+0, j+0)
          S2 = T2 + T5 - 4 * CA1(i+1, j+0)
          S3 = T3 + T6 - 4 * CA1(i+0, j+1)
          S4 = T4 + T7 - 4 * CA1(i+1, j+1)
          CA(i+0, j+0) = CA1(i+0, j+0) + DD * S1
          CA(i+1, j+0) = CA1(i+1, j+0) + DD * S2
          CA(i+0, j+1) = CA1(i+0, j+1) + DD * S3
          CA(i+1, j+1) = CA1(i+1, j+1) + DD * S4
        enddo
      enddo

The loop body executes 12 reads, whereas as the rolled loop shown in the previous section executes 20 reads to compute the same four values.

In code 3, two loops are unrolled 8 times and one loop is unrolled 4 times. Here is the before

  for (k = 0; k < NK[u]; k++) {
    sum = 0.0;
    for (y = 0; y < NY; y++) {
      sum += W[y][u][k] * delta[y];
    }
    backprop[i++]=sum;
  }

and after code

   for (k = 0; k < KK - 8; k+=8) {
      sum0 = 0.0;
      sum1 = 0.0;
      sum2 = 0.0;
      sum3 = 0.0;
      sum4 = 0.0;
      sum5 = 0.0;
      sum6 = 0.0;
      sum7 = 0.0;
      for (y = 0; y < NY; y++) {
         sum0 += W[y][0][k+0] * delta[y];
         sum1 += W[y][0][k+1] * delta[y];
         sum2 += W[y][0][k+2] * delta[y];
         sum3 += W[y][0][k+3] * delta[y];
         sum4 += W[y][0][k+4] * delta[y];
         sum5 += W[y][0][k+5] * delta[y];
         sum6 += W[y][0][k+6] * delta[y];
         sum7 += W[y][0][k+7] * delta[y];
      }
      backprop[k+0] = sum0;
      backprop[k+1] = sum1;
      backprop[k+2] = sum2;
      backprop[k+3] = sum3;
      backprop[k+4] = sum4;
      backprop[k+5] = sum5;
      backprop[k+6] = sum6;
      backprop[k+7] = sum7;
   }

for one of the loops unrolled 8 times.

Optimizing for temporal locality is the most difficult optimization considered in this paper. The concepts are not difficult, but the sweet spot is small. Identifying where the program can benefit from loop unrolling or loop fusion is not trivial. Moreover, it takes some effort to get it right. Still, educating scientific programmers about temporal locality and teaching them how to optimize for it will pay dividends.

Reducing instruction count

Execution time is a function of instruction count. Reduce the count and you usually reduce the time. The best solution is to use a more efficient algorithm; that is, an algorithm whose order of complexity is smaller, that converges quicker, or is more accurate. Optimizing source code without changing the algorithm yields smaller, but still significant, gains. This paper considers only the latter because the intent is to study how much better codes can run if written by programmers schooled in basic code optimization techniques.

The ten codes studied benefited from three types of "instruction reducing" optimizations. The two most prevalent were hoisting invariant memory and data operations out of inner loops. The third was eliminating unnecessary data copying. The nature of these inefficiencies is language dependent.

Memory operations

The semantics of C make it difficult for the compiler to determine all the invariant memory operations in a loop. The problem is particularly acute for loops in functions since the compiler may not know the values of the function's parameters at every call site when compiling the function. Most compilers support pragmas to help resolve ambiguities; however, these pragmas are not comprehensive and there is no standard syntax. To guarantee that invariant memory operations are not executed repetitively, the user has little choice but to hoist the operations by hand. The problem is not as severe in Fortran programs because in the absence of equivalence statements, it is a violation of the language's semantics for two names to share memory.

Codes 3 and 5 are C programs. In both cases, the compiler did not hoist all invariant memory operations from inner loops. Consider the following loop from code 3

   for (y = 0; y < NY; y++) {
      i = 0;
      for (u = 0; u < NU; u++) {
         for (k = 0; k < NK[u]; k++) {
            dW[y][u][k] += delta[y] * I1[i++];
         } 
      }
   }

Since dW[y][u] can point to the same memory space as delta for one or more values of y and u, assignment to dW[y][u][k] may change the value of delta[y]. In reality, dW and delta do not overlap in memory, so I rewrote the loop as

   for (y = 0; y < NY; y++) {
      i = 0;
      Dy = delta[y];
      for (u = 0; u < NU; u++) {
         for (k = 0; k < NK[u]; k++) {
            dW[y][u][k] += Dy * I1[i++];
         } 
      }
   }

Failure to hoist invariant memory operations may be due to complex address calculations. If the compiler can not determine that the address calculation is invariant, then it can hoist neither the calculation nor the associated memory operations. As noted above, code 5 uses a macro to address four-dimensional arrays

  #define MAT4D(a,q,i,j,k) (double *)((a)->data + (q)*(a)->strides[0] 
                          + (i)*(a)->strides[3] + (j)*(a)->strides[2] 
                          + (k)*(a)->strides[1])

The macro is too complex for the compiler to understand and so, it does not identify any subexpressions as loop invariant. The simplest way to eliminate the address calculation from the innermost loop (over i) is to define

  a0 = MAT4D(a,q,0,j,k)

before the loop and then replace all instances of

  *MAT4D(a,q,i,j,k) 
in the loop with
  a0[i]

A similar problem appears in code 6, a Fortran program. The key loop in this program is

    do n1 = 1, nh
    nx1 = (n1 - 1) / nz + 1
    nz1 = n1 - nz * (nx1 - 1)
        do n2 = 1, nh
            nx2 = (n2 - 1) / nz + 1
            nz2 = n2 - nz * (nx2 - 1)
            ndx = nx2 - nx1
            ndy = nz2 - nz1
            gxx = grn(1,ndx,ndy)
            gyy = grn(2,ndx,ndy)
            gxy = grn(3,ndx,ndy)
            balance(n1,1) = balance(n1,1) +
            (force(n2,1) * gxx + force(n2,2) * gxy) * h1
            balance(n1,2) = balance(n1,2) +
            (force(n2,1) * gxy + force(n2,2) * gyy)*h1
        end do
    end do

The programmer has written this loop well—there are no loop invariant operations with respect to n1 and n2. However, the loop resides within an iterative loop over time and the index calculations are independent with respect to time. Trading space for time, I precomputed the index values prior to the entering the time loop and stored the values in two arrays. I then replaced the index calculations with reads of the arrays.

Data operations

Ways to reduce data operations can appear in many forms. Implementing a more efficient algorithm produces the biggest gains. The closest I came to an algorithm change was in code 4. This code computes the inner product of K-vectors A(i) and B(j), 0 ≤ i < N, 0 ≤ j < M, for most values of i and j. Since the program computes most of the NM possible inner products, it is more efficient to compute all the inner products in one triply-nested loop rather than one at a time when needed. The savings accrue from reading A(i) once for all B(j) vectors and from loop unrolling.

   for (i = 0; i < N; i+=8) {
      for (j = 0; j < M; j++) {
         sum0 = 0.0;
         sum1 = 0.0;
         sum2 = 0.0;
         sum3 = 0.0;
         sum4 = 0.0;
         sum5 = 0.0;
         sum6 = 0.0;
         sum7 = 0.0;
         for (k = 0; k < K; k++) {
            sum0 += A[i+0][k] * B[j][k];
            sum1 += A[i+1][k] * B[j][k];
            sum2 += A[i+2][k] * B[j][k];
            sum3 += A[i+3][k] * B[j][k];
            sum4 += A[i+4][k] * B[j][k];
            sum5 += A[i+5][k] * B[j][k];
            sum6 += A[i+6][k] * B[j][k];
            sum7 += A[i+7][k] * B[j][k];
         }
         C[i+0][j] = sum0;
         C[i+1][j] = sum1;
         C[i+2][j] = sum2;
         C[i+3][j] = sum3;
         C[i+4][j] = sum4;
         C[i+5][j] = sum5;
         C[i+6][j] = sum6;
         C[i+7][j] = sum7;
      }}

This change requires knowledge of a typical run; i.e., that most inner products are computed. The reasons for the change, however, derive from basic optimization concepts. It is the type of change easily made at development time by a knowledgeable programmer.

In code 5, we have the data version of the index optimization in code 6. Here a very expensive computation is a function of the loop indices and so cannot be hoisted out of the loop; however, the computation is invariant with respect to an outer iterative loop over time. We can compute its value for each iteration of the computation loop prior to entering the time loop and save the values in an array. The increase in memory required to store the values is small in comparison to the large savings in time.

The main loop in Code 8 is doubly nested. The inner loop includes a series of guarded computations; some are a function of the inner loop index but not the outer loop index while others are a function of the outer loop index but not the inner loop index

   for (j = 0; j < N; j++) {
      for (i = 0; i < M; i++) {
         r = i * hrmax;
         R = A[j];
         temp = (PRM[3] == 0.0) ? 1.0 : pow(r, PRM[3]);
         high = temp * kcoeff * B[j] * PRM[2] * PRM[4];
         low = high * PRM[6] * PRM[6] /
         (1.0 + pow(PRM[4] * PRM[6], 2.0));
         kap = (R > PRM[6]) ?
         high * R * R / (1.0 + pow(PRM[4]*r, 2.0) :
         low * pow(R/PRM[6], PRM[5]);
   
      < rest of loop omitted >
      }}


Note that the value of temp is invariant to j. Thus, we can hoist the computation for temp out of the loop and save its values in an array.

   for (i = 0; i < M; i++) {
      r = i * hrmax;
      TEMP[i] = pow(r, PRM[3]);
   }

[N.B. – the case for PRM[3] = 0 is omitted and will be reintroduced later.] We now hoist out of the inner loop the computations invariant to i. Since the conditional guarding the value of kap is invariant to i, it behooves us to hoist the computation out of the inner loop, thereby executing the guard once rather than M times. The final version of the code is

   for (j = 0; j < N; j++) {
      R = rig[j] / 1000.;
      tmp1 = kcoeff * par[2] * beta[j] * par[4];
      tmp2 = 1.0 + (par[4] * par[4] * par[6] * par[6]);
      tmp3 = 1.0 + (par[4] * par[4] * R * R);
      tmp4 = par[6] * par[6] / tmp2;
      tmp5 = R * R / tmp3;
      tmp6 = pow(R / par[6], par[5]);
      if ((par[3] == 0.0) && (R > par[6])) {
         for (i = 1; i <= imax1; i++)
            KAP[i] = tmp1 * tmp5;
         } else if ((par[3] == 0.0) && (R <= par[6])) {
            for (i = 1; i <= imax1; i++)
               KAP[i] = tmp1 * tmp4 * tmp6;
         } else if ((par[3] != 0.0) && (R > par[6])) {
             for (i = 1; i <= imax1; i++)
               KAP[i] = tmp1 * TEMP[i] * tmp5;
         } else if ((par[3] != 0.0) && (R <= par[6])) {
             for (i = 1; i <= imax1; i++)
               KAP[i] = tmp1 * TEMP[i] * tmp4 * tmp6;
      }             

      for (i = 0; i < M; i++) {
         kap = KAP[i];
         r = i * hrmax;
         < rest of loop omitted >
      }
   }

Maybe not the prettiest piece of code, but certainly much more efficient than the original loop,

Copy operations

Several programs unnecessarily copy data from one data structure to another. This problem occurs in both Fortran and C programs, although it manifests itself differently in the two languages.

Code 1 declares two arrays—one for old values and one for new values. At the end of each iteration, the array of new values is copied to the array of old values to reset the data structures for the next iteration. This problem occurs in Fortran programs not included in this study and in both Fortran 77 and Fortran 90 code.

Introducing pointers to the arrays and swapping pointer values is an obvious way to eliminate the copying; but pointers is not a feature that many Fortran programmers know well or are comfortable using. An easy solution not involving pointers is to extend the dimension of the value array by 1 and use the last dimension to differentiate between arrays at different times. For example, if the data space is N x N, declare the array (N, N, 2). Then store the problem’s initial values in (_, _, 2) and define the scalar names new = 2 and old = 1. At the start of each iteration, swap old and new to reset the arrays.

The old–new copy problem did not appear in any C program. In programs that had new and old values, the code swapped pointers to reset data structures. Where unnecessary coping did occur is in structure assignment and parameter passing. Structures in C are handled much like scalars. Assignment causes the data space of the right-hand name to be copied to the data space of the left-hand name. Similarly, when a structure is passed to a function, the data space of the actual parameter is copied to the data space of the formal parameter. If the structure is large and the assignment or function call is in an inner loop, then copying costs can grow quite large. While none of the ten programs considered here manifested this problem, it did occur in programs not included in the study. A simple fix is always to refer to structures via pointers.

Optimizing loop structures

Since scientific programs spend almost all their time in loops, efficient loops are the key to good performance. Conditionals, function calls, little instruction level parallelism, and large numbers of temporary values make it difficult for the compiler to generate tightly packed, highly efficient code. Conditionals and function calls introduce jumps that disrupt code flow. Users should eliminate or isolate conditionls to their own loops as much as possible. Often logical expressions can be substituted for if-then-else statements. For example, code 2 includes the following snippet

      MaxDelta = 0.0
      do J = 1, N
        do I = 1, M
          < code omitted >
          Delta = abs(OldValue ? NewValue)
          if (Delta > MaxDelta) MaxDelta = Delta
        enddo
      enddo

      if (MaxDelta .gt. 0.001) goto 200

Since the only use of MaxDelta is to control the jump to 200 and all that matters is whether or not it is greater than 0.001, I made MaxDelta a boolean and rewrote the snippet as

      MaxDelta = .false.
      do J = 1, N
        do I = 1, M
          < code omitted >
          Delta = abs(OldValue ? NewValue)
          MaxDelta = MaxDelta .or. (Delta .gt. 0.001)
        enddo
      enddo

      if (MaxDelta) goto 200

thereby, eliminating the conditional expression from the inner loop.

A microprocessor can execute many instructions per instruction cycle. Typically, it can execute one or more memory, floating point, integer, and jump operations. To be executed simultaneously, the operations must be independent. Thick loops tend to have more instruction level parallelism than thin loops. Moreover, they reduce memory traffice by maximizing data reuse. Loop unrolling and loop fusion are two techniques to increase the size of loop bodies. Several of the codes studied benefitted from loop unrolling, but none benefitted from loop fusion. This observation is not too surpising since it is the general tendency of programmers to write thick loops.

As loops become thicker, the number of temporary values grows, increasing register pressure. If registers spill, then memory traffic increases and code flow is disrupted. A thick loop with many temporary values may execute slower than an equivalent series of thin loops. The biggest gain will be achieved if the thick loop can be split into a series of independent loops eliminating the need to write and read temporary arrays. I found such an occasion in code 10 where I split the loop

      do i = 1, n
        do j = 1, m
          A24(j,i)= S24(j,i) * T24(j,i) + S25(j,i) * U25(j,i)
          B24(j,i)= S24(j,i) * T25(j,i) + S25(j,i) * U24(j,i)
          A25(j,i)= S24(j,i) * C24(j,i) + S25(j,i) * V24(j,i)
          B25(j,i)= S24(j,i) * U25(j,i) + S25(j,i) * V25(j,i)
          C24(j,i)= S26(j,i) * T26(j,i) + S27(j,i) * U26(j,i)
          D24(j,i)= S26(j,i) * T27(j,i) + S27(j,i) * V26(j,i)
          C25(j,i)= S27(j,i) * S28(j,i) + S26(j,i) * U28(j,i)
          D25(j,i)= S27(j,i) * T28(j,i) + S26(j,i) * V28(j,i)
        end do
      end do

into two disjoint loops

      do i = 1, n
        do j = 1, m
          A24(j,i)= S24(j,i) * T24(j,i) + S25(j,i) * U25(j,i)
          B24(j,i)= S24(j,i) * T25(j,i) + S25(j,i) * U24(j,i)
          A25(j,i)= S24(j,i) * C24(j,i) + S25(j,i) * V24(j,i)
          B25(j,i)= S24(j,i) * U25(j,i) + S25(j,i) * V25(j,i)
        end do
      end do
      
      do i = 1, n
        do j = 1, m
          C24(j,i)= S26(j,i) * T26(j,i) + S27(j,i) * U26(j,i)
          D24(j,i)= S26(j,i) * T27(j,i) + S27(j,i) * V26(j,i)
          C25(j,i)= S27(j,i) * S28(j,i) + S26(j,i) * U28(j,i)
          D25(j,i)= S27(j,i) * T28(j,i) + S26(j,i) * V28(j,i)
        end do
      end do

Conclusions

Over the course of the last year, I have had the opportunity to work with over two dozen academic scientific programmers at leading research universities. Their research interests span a broad range of scientific fields. Except for two programs that relied almost exclusively on library routines (matrix multiply and fast Fourier transform), I was able to improve significantly the single processor performance of all codes. Improvements range from 2x to 15.5x with a simple average of 4.75x. Changes to the source code were at a very high level. I did not use sophisticated techniques or programming tools to discover inefficiencies or effect the changes. Only one code was parallel despite the availability of parallel systems to all developers.

Clearly, we have a problem—personal scientific research codes are highly inefficient and not running parallel. The developers are unaware of simple optimization techniques to make programs run faster. They lack education in the art of code optimization and parallel programming. I do not believe we can fix the problem by publishing additional books or training manuals. To date, the developers in questions have not studied the books or manual available, and are unlikely to do so in the future.

Short courses are a possible solution, but I believe they are too concentrated to be much use. The general concepts can be taught in a three or four day course, but that is not enough time for students to practice what they learn and acquire the experience to apply and extend the concepts to their codes. Practice is the key to becoming proficient at optimization.

I recommend that graduate students be required to take a semester length course in optimization and parallel programming. We would never give someone access to state-of-the-art scientific equipment costing hundreds of thousands of dollars without first requiring them to demonstrate that they know how to use the equipment. Yet the criterion for time on state-of-the-art supercomputers is at most an interesting project. Requestors are never asked to demonstrate that they know how to use the system, or can use the system effectively. A semester course would teach them the required skills. Government agencies that fund academic scientific research pay for most of the computer systems supporting scientific research as well as the development of most personal scientific codes. These agencies should require graduate schools to offer a course in optimization and parallel programming as a requirement for funding.



About the Author

John Feo received his Ph.D. in Computer Science from The University of Texas at Austin in 1986. After graduate school, Dr. Feo worked at Lawrence Livermore National Laboratory where he was the Group Leader of the Computer Research Group and principal investigator of the Sisal Language Project. In 1997, Dr. Feo joined Tera Computer Company where he was project manager for the MTA, and oversaw the programming and evaluation of the MTA at the San Diego Supercomputer Center. In 2000, Dr. Feo joined Sun Microsystems as an HPC application specialist. He works with university research groups to optimize and parallelize scientific codes. Dr. Feo has published over two dozen research articles in the areas of parallel parallel programming, parallel programming languages, and application performance.

Friday Feb 11, 2011

On the Spot!

SPOT ArchitectureOne of the new tools in the latest 12.2 release of Oracle Solaris Studio is SPOT -  The Simple Performance Optimization Tool.

SPOT simplifies the process of performance analysis by running an application under a common set of tools and producing HTML reports of its findings, which provides the following benefits:

  • By creating reports in HTML format, SPOT lets you place the reports on a server that can be accessed by an entire development team. For example, a SPOT report can be examined by remote colleagues, or referred to during a meeting. You could even email a URL of a particular line of source code, or disassembly, to a colleague for further review.

  • The SPOT report archives the compiler build commands as well as the profile for the active parts of the application. By comparing the current application profile with an older profile, you can easily check for changed code or changed compiler build flags.

  • SPOT can also profile the application according to the most frequently occurring hardware events, indicating which routines are encountering which problems.

Complete documentation on SPOT is here

Wednesday Feb 02, 2011

Where To Find Oracle Solaris Studio Resources

Here's where to find information and discussions for the latest Oracle Solaris Studio compilers and tools at it's new home on the Oracle Technical Network (OTN):

There are also pages focused on primary topics regarding Solaris Studio compilers and tools:

Building
Oracle Solaris Studio C, C++, and Fortran compilers include advanced features for building applications on Oracle Solaris SPARC and x86/x64 platforms.

Debugging
Successful program debugging is more an art than a science. dbx is an interactive, source-level, post-mortem and real-time command-line debugging tool plus much more.

Analyzing
Performance analysis is the first step toward program optimization. Oracle Solaris Studio Performance Analyzer can help you assess the performance of your code, identify potential performance problems, and locate the part of the code where the problems occur.

Tuning
Oracle Solaris Studio C, C++, and Fortran compilers offer a rich set of compile-time options for specifying target hardware and advanced optimization techniques. 

Multicore/Parallel Programming
High Performance and Technical Computing (HPTC) applies numerical computation techniques to highly complex scientific and engineering problems. Oracle Solaris Studio compilers and tools provide a seamless, integrated environment from desktop to TeraFLOPS for both floating-point and data-intensive computing.

Computing
The floating-point environment on Oracle Sun SPARC and x86/x64 platforms enables you to develop robust, high-performance, portable numerical applications. The floating-point environment can also help investigate unusual behavior of numerical programs written by others. The Sun Performance Library provides highly optimized versions of many advanced math function routines.

Still under development, there's more to do. Open for suggestions.


Tuesday Oct 13, 2009

HPC Profiling for Fun and Profit

Just released:

HPC Profiling with the Sun Studio Performance Tools
Marty Itzkowitz and Yukon Maruyama (Sun Microsystems) describe how to use the Sun Studio Performance Tools to understand the performance issues in single-threaded, multi-threaded,  OpenMP, and MPI applications, and the techniques used to profile them. This paper was presented at the Third Parallel Tools Workshop held in Dresden Germany in September.

The link to the article is:

http://developers.sun.com/sunstudio/documentation/techart/hpc_profiling.pdf

Monday Feb 16, 2009

Feedback

Another useful optimization option available with Sun Studio compilers is profile feedback.

This option can be especially helpful with codes that contain a lot of branching. The compiler is unable to determine from the source code alone which branches in an IF or CASE statement are the most likely to be taken. Using the profile feedback feature, you can run an instrumented version of the code using typical data to collect statistics on code coverage and branching, and then recompile the code using this collected data.

Darryl Gove has a great description of profile feedback in his book Solaris Application Programming.

With profile feedback, the compiler is better able to do certain optimizations that it cannot do by just analyzing the source code:

  • Layout the compiled code so that branches are rarely taken. The most frequent branches "fall-through" to the next memory location, avoiding a fetch and branch to a distant location.
  • Inline routines called many times. This avoids costly function calls.
  • Move infrequently executed code out of the "hot" parts of the code. This improves utilization of the instruction cache.
  • Lots more optimizations based on how variables are and are not utilized, based on the mostly likely paths the program will take

Of course, all these optimizations will depend on the typicality of the test data collected in the profile. Some cases it might be useful to identify a set of "typical data", collect data for each set, and compile multiple versions using each profile. Of course, this all depends on the application.

To use profile feedback, the compilation is in three phases:

  1. Compile with -xprofile=collect to produce an instrumented executable.
  2. Run the instrumented executable with a typical data set to create a performance profile.
  3. Recompile with -xprofile=use and -xO5 to produce the optimized executable

 % cc -xO3 -xprofile=collect:/tmp/profile myapp.c
 % a.out
 % cc -xO5 -xprofile=use:/tmp/profile -o myapp myapp.c


Read about profile feedback in the compiler man pages: C++, C, Fortran

Tuesday Jan 13, 2009

What Am I Compiling For?

It's worth thinking about the target processor you intend your code to run on. If performance is not an issue, then you can go with whatever default the compiler offers. But overall performance will improve if you can be more specific about the target hardware.

Both SPARC and x86 processors have 32-bit and 64-bit modes. Which is best for your code? And are you letting the compiler generate code that utilizes the full instruction set of the target processor?

32-bit mode is fine for most applications, and it will run even if the target system is running in 64-bit mode. But the opposite is not true .. to run an application compiled for 64-bit it must be run on a system with a 64-bit kernel, it will get errors on a 32-bit system.

How do you find out if the (Solaris) system you're running on is in 32-bit or 64-bit mode? Use the isainfo -k command:

 >isainfo -v
64-bit sparcv9 applications
        vis2 vis
32-bit sparc applications
        vis2 vis v8plus div32 mul32

This SPARC system is running in 64-bit mode. The command also tells me that this processor has the VIS2 instruction set.

On another system, isainfo reports this:

 >isainfo -v
64-bit amd64 applications
    sse2 sse fxsr amd_3dnowx amd_3dnow amd_mmx mmx cmov amd_sysc cx8 tsc fpu
32-bit i386 applications
    sse2 sse fxsr amd_3dnowx amd_3dnow amd_mmx mmx cmov amd_sysc cx8 tsc fpu

On UltraSPARC systems, the only advantage to running a code in 64-bit mode is the ability to access very large address spaces. Otherwise there is very little performance gain, and some codes might even run slower. On x86/x64 systems, there is the added advantage of being able to utilize additional machine instructions and additional registers. For both, compiling for 64-bit may increase the binary size of the program (long data and pointers become 8 instead of 4 bytes). But if you're intending your code to run on x86/x64 systems, compiling for 64-bit is probably a good idea. It might even run faster.

So how do you do it?

The compiler options -m64 and -m32 specify compiling for 64-bit or 32-bit execution. And it's important to note that 64-bit and 32-bit objects and libraries cannot be intermixed in a single executable. Also, on Solaris systems -m32 is the default, but on 64-bit x64 Linux systems -m64 -xarch=sse2 is the default.

>f95 -m32 -o ran ran.f
>file ran
ran:    ELF 32-bit LSB executable 80386 Version 1 [FPU], dynamically linked, not stripped
>f95 -m64 -o ran64 ran.f
>file ran64
ran64:  ELF 64-bit LSB executable AMD64 Version 1 [SSE FXSR FPU], dynamically linked, not stripped

It's also most helpful to tell the compiler what processor you're intend to run the application on. The default is to produce a generic binary that will run well on most current processors. But that leaves out a lot of opportunities for optimization. As newer and newer processors are made available, new machine instructions or other hardware features are added to the basic architecture to improve performance. The compiler needs to be told whether or not to utilize these new features. However this can produce backward incompatibilities, rendering the binary code unable to run on older systems. To handle this, application developers will make various binary versions available for current and legacy platforms.

For example, if you compile with the -fast option, the compiler will generate the best code it can for the processor it is compiling on. -fast   includes -xtarget=native. You can override this choice by adding a different -xtarget after the -fast option on the command line (the command line is processed from left to right).  For example, to compile for an UltraSPARC T2 system when that is not the native system you are compiling on, use -fast -xtarget=ultraT2.

New processors appear on the scene often. And with each new release of the Sun Studio compilers, the list of -xtarget options expands to handle them.  These new processor values are usually announced in the Sun Studio compiler READMEs. Tipping the compiler about the target processor helps performance.

More about -xtarget and what it means next time.

(For details, check the compiler man pages)

Saturday Jan 10, 2009

What Am I Optimizing?

Let's think about this a little bit more.

If I add an optimization option, like -xO3 or -fast, to my compile command-line, what does that actually mean?

Well, it means that everything in that compilation unit (source files) will be compiled with a certain set of optimization stragegies. The compiler will try to produce the best code it can at that level. But ambiguities in the source code might inhibit some optimizations because the compiler has to make sure that the machine code it generates will always do the right thing .. that is, do what the programmer expects it to do.

Note that all the routines, functions, modules, procedures, classes, compiled in that compilation unit will be compiled with the same options. In some cases the extra time spent by the compiler might be wasted on some routines because they are rarely called and do not really participate in the compute-intensive parts of the program.

For short programs, this hardly matters .. compile time is short, and you might only compile infrequently.

But this can become an issue with "industrial-strength" codes consisting of thousands of lines, hundreds of program units (routines, functions, etc..). Compile time might become a major concern, so we probably would want to compile only those routines that factor into the overall performance of the complete program.

That means you really need to know where your program is spending most of it's CPU time, and focus your performance optimization efforts primarily on those program units. This goes for any kind of performance optimization .. you do need to know and understand the flow of the program -- its footprint.

The Sun Studio Performance Analyzer is the tool to do that. While it does provide extensive features for gathering every piece of information about your program's execution, it also has a simple command-line interface that you can use immediately to find out where the program is spending most of its time.

Compile your code with the -g option (to produce a symbol table) and run the executable under the collect command.

>f95 -g -fixed -o shal shalow.f90

>collect shal

Creating experiment database test.1.er ...

1NUMBER OF POINTS IN THE X DIRECTION     256

 NUMBER OF POINTS IN THE Y DIRECTION     256

....

Running under the collect command generates runtime execution data in test.1.er/ that can be used by the er_print command of the Performance Analyzer:

>er_print -functions test.1.er
Functions sorted by metric: Exclusive User CPU Time

Excl.     Incl.      Name  
User CPU  User CPU         
  sec.      sec.      
18.113    18.113     <Total>
 6.805     6.805     calc1_
 6.384     6.384     calc2_
 4.893     4.893     calc3_
 0.020     0.020     inital_
 0.010     0.010     calc3z_
 0.        0.        cosf
 0.        0.        cputim_
 0.        0.        etime_
 0.        0.        getrusage
 0.       18.113     main
 0.       18.113     MAIN
 0.        0.        __rusagesys
 0.        0.        sinf
 0.       18.113     _start


The er_print -functions command gives us a quick way of seeing timings for all routines (this was a Fortran 95 program), including library routines. Right away I know that calc1, calc2, and calc3 do all the work, as expected. But we also see that calc3 is not as significant as calc1. ("Inclusive Time" includes time spent in the routines called by that routine, while "Exclusive Time" only counts time spent in the routine, exclusive of any calls to other routines.)

Well, this is a start. Note that no optimization was specified here. Lets see what happens with -fast.

>f95 -o shalfast -fast -fixed -g shalow.f90
>collect shalfast
Creating experiment database test.3.er ...
....
>er_print -functions test.3.er
Functions sorted by metric: Exclusive User CPU Time

Excl.     Incl.      Name  
User CPU  User CPU         
 sec.      sec.       
7.695     7.695      <Total>
7.675     7.695      MAIN
0.020     0.020      __rusagesys
0.        0.020      etime_
0.        0.020      getrusage



Yikes! What happened?

Clearly, with -fast the compiler compressed the program as much as it could, replacing the calls to the calc routines by compiling them inline into one hunk of code. Note also the 2x improvement in performance.

Of course, this was a little toy test program. Things would look a lot more complicated with a large "industrial" program.

But you get the idea.

More information on er_print and collect.

Friday Jan 09, 2009

Optimization Levels

Sun Studio compilers provide five levels of optimization, -xO1 thru -xO5, and each increasing level adds more optimization strategies for the compiler, with -xO5 being the highest level.

And, the higher the optimization level the higher the compilation time, depending on the complexity of the source code, which is understandable because the compiler has to do more.

The default when an optimization level is not specified on the command line, is to do no optimization at all. This is good when you just want to get the code to compile, checking for syntax errors in the source and the right runtime behavior, with minimal compile time.

So, if you are concerned about runtime performance you need to specify an optimization level at compile time. A good starting point is to use the -fast macro, as described in an earlier post, which includes -xO5, the highest optimization level. Or, compile with an explicit level, like -xO3, which provides a reasonable amount of optimization without increasing compilation time significantly.

But keep in mind that the effectiveness of the compiler's optimization strategies depend on the source code being compiled. This is especially true in C and C++ where the use of pointers can frustrate the compiler's attempt at generating optimimal code due to the side effects such optimizations can cause. (But, of course, there are other options, like -xalias_level,  you can use to help the compiler make assumptions about the use of pointers in the source code.)

Another concern is whether or not you might need to use the debugger, dbx, during or after execution of the program.  For the debugger to provide useful information, it needs to see the symbol tables and linker data that are usually thrown away after compilation. The -g debug option preserves these tables in the executable file so the debugger can read them and associate the binary dump file with the symbolic program.

But the optimized code that the compiler generates may mix things up so that it's hard to tell where the code for one source statement starts and another ends. So that's why the compiler man pages talk a lot about the interaction between optimization levels and debugging. With optimization levels greater than 3,  the compiler provides best-effort symbolic information for the debugger.

Bottom line, you almost always get better performance by specifying an optimization level (or -fast which includes -xO5) on the compile command.

(Find out more...)

Thursday Jan 08, 2009

Optimization Shortcut with -fast

So if I've got a code and I've already compiled it without any real options, so I know it will compile, where do I start with trying to get the best performance?

Well, the Sun Studio compilers have many options for performance optimization. You can try them all one by one and see what works. 

Or, you can start off by compiling with -fast.

-fast is a macro -- it's a set of options that are all invoked simultaneously. Some of the options that it uses can be problematic for some codes. Also, compiling with -fast may increase compile time. But the resulting executable should run faster than compiling with default options for most codes.

Also, the set of options that make up -fast are different for each compiler and on whether you're compiling on a SPARC or x86/x64 processor.

One way to see what the component options of -fast are is by using the compiler's -dryrun or -# options

For example, on a SPARC Solaris system:

edgard:/home/rchrd<42>f95 -dryrun -fast | grep ###
###     command line files and options (expanded):
### -dryrun -xO5 -xarch=sparcvis2 -xcache=64/32/4:1024/64/4 -xchip=ultra3i -xpad=local -xvector=lib -dalign -fsimple=2 -fns=yes -ftrap=common -xlibmil -xlibmopt -fround=nearest

edgard:/home/rchrd<43>CC -dryrun -fast | grep ###
###     command line files and options (expanded):
### -dryrun -xO5 -xarch=sparcvis2 -xcache=64/32/4:1024/64/4 -xchip=ultra3i -xmemalign=8s -fsimple=2 -fns=yes -ftrap=%none -xlibmil -xlibmopt -xbuiltin=%all -D__MATHERR_ERRNO_DONTCARE


On my AMD64 OpenSolaris laptop we see:

FerrariOS:/export/home/rchrd<25>CC -dryrun -fast | grep ###
###     command line files and options (expanded):
### -dryrun -xO5 -xarch=sse3a -xcache=64/64/2:1024/64/16 -xchip=opteron -xdepend=yes -fsimple=2 -fns=yes -ftrap=%none -xlibmil -xlibmopt -xbuiltin=%all -D__MATHERR_ERRNO_DONTCARE -nofstore -xregs=frameptr -Qoption CC -iropt -Qoption CC -xcallee64

FerrariOS:/export/home/rchrd<22>cc -fast -# no.c |& grep ###
###     command line files and options (expanded):
### -D__MATHERR_ERRNO_DONTCARE -fns -nofstore -fsimple=2 -fsingle -xalias_level=basic -xarch=sse3a -xbuiltin=%all -xcache=64/64/2:1024/64/16 -xchip=opteron -xdepend -xlibmil -xlibmopt -xO5 -xregs=frameptr no.c



The particular options are chosen to get the best performance on the host platform ... so this assumes that you're going to run the executable binary on the same processor that compiled it.

I have one computationally intensive Fortran 95 program that runs on an UltraSPARC IIIi system in 54.4 seconds using just default compiler options. Just adding -fast to the compile command line gives me an executable that runs in only 12.2 seconds .. almost one-fifth the time.  The same program on my AMD64 laptop runs one-third as fast with -fast than without it.

But you do have to be careful. Check the manuals, which caution:

Because -fast invokes -dalign, -fns, -fsimple=2, programs compiled with -fast can result in nonstandard floating-point arithmetic, nonstandard alignment of data, and nonstandard ordering of expression evaluation. These selections might not be appropriate for most programs.

Looks like we we may have some more explaining to do.

 
  

About


Deep thoughts on compiling C, C++, and Fortran codes with Oracle Solaris Studio compilers, especially optimization and parallelization, from the Solaris Studio documentation lead, Richard Friedman. Email him at
Richard dot Friedman at Oracle dot com

When Run Was A Compiler

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today