apeNEXT optimization HOWTO

There exist two tools to statically analyse the optimization of an apeNEXT program. The nperf script can give you a rough overview of how many instructions the different functions use and how well the floating point unit is used. The exact execution order of the instructions is written in the microcode, which can be looked at with the dispminit script.

nperf -asm=sourcefile.sasm -c -l -a sourcefile-sofan.mem > sourcefile-sofan.perf

dispminit sourcefile-sofan.mem > sourcefile-sofan.ncd

Dynamic analysis of the code means to run it on apeNEXT and query the runtime counters. In contrast to the static analysis you also gather information on how long the processor was stalling, i.e. waiting for some thing to happen, for example data arriving from memory. This can help to identify memory/network bottlenecks and gives the most significant measure of how well the code is optimized.

See HOWTO-runcounters for details.

The first optimization we will apply is to put the code of the loop body into the cache. This tells the processor to load the instructions only once at the beginning of the loop, instead of every time the loop body is exectuted. Since the instructions are situated in the same memory as the data, instruction loading would otherwise compete with loading of data into the processor.

We instruct the compiler to do this via the #pragma cache, which is a special syntax extension added to the C compiler for apeNEXT.

The downside of this instruction caching is that during the loading procedure of instructions into the cache, no other operations can be performed. It follows that instruction caching only makes sense if the loop body is going to be executed many times.

  {
#pragma cache
    for (i=0; i<VOLUME; i++) {
      sp+=conj(in1[i])*conj(in2[i]);
    }
  }

Now the nperf output is

The runtime counters are (divided by the volume)

A loop produces at the beginning and end of the loop body some overhead, which can become significant if the body itself is very small. It is therefore helpful to duplicate the body, either explicitly or by a pragma that has been introduced for apeNEXT. Here we use the pragma

  {
#pragma cache
    {
#pragma unroll 8
      for (i=0; i<VOLUME; i++) {
	sp+=conj(in1[i])*in2[i];
      }
    }
  }

The runtime counters are (divided by the volume)

The next step is to improve the memory access. For every single pull from memory the processor has to load the address into a specific register and then initiate the memory access. A subsequent access can then be processed at the earliest 4 clock cycles later. But we can instruct the processor to load a bigger amount of data into the register with one intruction. We therefore define a new type which holds (for example) 8 complex numbers:

typedef struct {
  complex c[8];
} b8complex;

complex scalar_product_burst_cache(complex * in1, complex * in2) {
  register int i;
  register complex sp=0.;
  register b8complex a1, a2;

  {
#pragma cache
    {
      for (i=0; i<VOLUME; i+=8) {
        a1=*((b8complex *) &in1[i]);
        a2=*((b8complex *) &in2[i]);
        sp+=conj(a1.c[0])*a2.c[0];
        sp+=conj(a1.c[1])*a2.c[1];
        sp+=conj(a1.c[2])*a2.c[2];
        sp+=conj(a1.c[3])*a2.c[3];
        sp+=conj(a1.c[4])*a2.c[4];
        sp+=conj(a1.c[5])*a2.c[5];
        sp+=conj(a1.c[6])*a2.c[6];
        sp+=conj(a1.c[7])*a2.c[7];
      }
    }
  }
  return sp;
}

This results in the nperf output for the loop

The runtime counters are (divided by the volume)

The apeNEXT processor is capable of doing one CNORM operation (like c1*c2+c3) per clock cycle, but the result will not be available immediately in the following cycle. As a consequence, each summation in the above example has to wait for the calculation of the previous line, resulting in a long waiting time. A better approach is to remove the dependencies of the calculations by having one variable for each summation, and add up the partial sums after the end of the loop:

  for (i=0; i<VOLUME; i+=8) {
    a1=*((b8complex *) &in1[i]);
    a2=*((b8complex *) &in2[i]);
    sp0+=conj(a1.c[0])*a2.c[0];
    sp1+=conj(a1.c[1])*a2.c[1];
    sp2+=conj(a1.c[2])*a2.c[2];
    sp3+=conj(a1.c[3])*a2.c[3];
    sp4+=conj(a1.c[4])*a2.c[4];
    sp5+=conj(a1.c[5])*a2.c[5];
    sp6+=conj(a1.c[6])*a2.c[6];
    sp7+=conj(a1.c[7])*a2.c[7];
  }
  //partial sum
  sp0=sp0+sp1;
  sp2=sp2+sp3;
  sp4=sp4+sp5;
  sp6=sp6+sp7;

  sp0=sp0+sp2;
  sp4=sp4+sp6;
  return sp0+sp4;

The nperf output for the loop is

The runtime counters are (divided by the volume)

To reduce waiting time for memory accesses, it may be beneficial to use prefetching. The memory access is initiated in one iteration and will then be used in the following iteration.

complex sp_cache_prefetch(complex * in1, complex * in2) {
  register int i;
  register complex sp=0, a1, a2, *rin1, *rin2;
  // Copy adresses to register
  rin1=in1; rin2=in2;

  // prefetch values for first iteration
  prefetch(*((double *) &(rin1[0])));
  prefetch(*((double *) &(rin2[0])));
  {
#pragma cache
    {
      for (i=1; i<VOLUME+1; i++) {
        asm("\tPRAGMA_FREE_QTR");
        prefetch(*((double *) &(rin1[i])));
        prefetch(*((double *) &(rin2[i])));
        fetch(a1);
        fetch(a2);
        sp+=conj(a1)*a2;
      }
    }
  }
  // fetch data that was prefetched in last iteration to emtpy the queue
  fetch(a1);
  fetch(a2);

  return sp;

The nperf output for the loop is

The runtime counters are (divided by the volume)

Using all optimization techniques together, the code could look like this

complex sp_cache_burst_partial_prefetch_unroll(complex * in1, complex * in2) {
  register complex sp0,sp1,sp2,sp3,sp4,sp5,sp6,sp7,*rin1,*rin2;
  register b8complex a1, a2;
  register int i,j;
  register int ind;

  // Copy adresses to register
  rin1=in1; rin2=in2;

  // prefetch values for first iteration
  {
#pragma unroll
    for (i=0; i<8*8; i+=) {
      prefetch(*((b8complex *) &(rin1[i])));
      prefetch(*((b8complex *) &(rin2[i])));
    }
  }
  sp0=0.; sp1=0.; sp2=0.; sp3=0.;
  sp4=0.; sp5=0.; sp6=0.; sp7=0.;
  
  {
#pragma cache
    {
#pragma unroll 8
      for (i=8*8; i<VOLUME+8*8; i+=8) {
	asm("\tPRAGMA_FREE_QTR");
	prefetch(*((b8complex *) &(rin1[i])));
	prefetch(*((b8complex *) &(rin2[i])));
	fetch(a1);
	fetch(a2);
	sp0+=conj(a1.c[0])*a2.c[0];
	sp1+=conj(a1.c[1])*a2.c[1];
	sp2+=conj(a1.c[2])*a2.c[2];
	sp3+=conj(a1.c[3])*a2.c[3];
	sp4+=conj(a1.c[4])*a2.c[4];
	sp5+=conj(a1.c[5])*a2.c[5];
	sp6+=conj(a1.c[6])*a2.c[6];
	sp7+=conj(a1.c[7])*a2.c[7];
      }
    }
  }
  // fetch data that was prefetched in last iteration to emtpy the queue
  {
#pragma unroll
    for (j=0; j<8; j++) {
      fetch(a1);
      fetch(a2);
    }
  }

  //partial sum
  sp0=sp0+sp1;
  sp2=sp2+sp3;
  sp4=sp4+sp5;
  sp6=sp6+sp7;

  sp0=sp0+sp2;
  sp4=sp4+sp6;

  return sp0+sp4;
}

The nperf output for the loop is

The runtime counters are (divided by the volume)