Case Study: High Performance Computing

In this lecture, we discuss a first case study of the application of C: High Performance Computing (HPC). You can access the slides 🖼️ for this lecture.

C in HPC

C is extensively used in HPC because it is fast. This speed is due to many reasons. Contrary to more high-level programming languages (e.g. Python):

First, C is close to the hardware — there are few layers to traverse when calling system functions:

With Python, your script needs to run through the interpreter. With Java, things are similar with the JVM: these additional layers in high-level languages introduce many overheads compared to low-level ones such as C.

Another source of overheads in high-level languages like Python or Java is automatic memory protection and management. For example, languages such as Java or Python have a garbage collector that automatically takes care of dynamic memory management tasks. To enforce memory safety, these languages also perform bounds checking, e.g. when indexing an array. In C, memory management is manual: there is no garbage collector, and there is also no memory protection. Although this creates more burden for the programmer, C avoids the related overheads in order to maximise execution speed.

Another advantage of C is that it is very easy to integrate with assembly, which sometimes needs to be used to optimise specific operations for performance.

And last but not least, C gives the programmer control over the data memory layout. We discuss this particular aspect in this lecture, showing how useful it can be when optimising a program for performance.

Memory Hierarchy 101

Here is a quick recap of a subset of the memory hierarchy present on all computers:

The CPU has local memory in the form of registers; there are very few of these, between 10 and 30, and accessing them is very fast: data present in registers is instantaneously available for computations. Main memory stores most of the program data because it is large, so bringing data from memory to registers for computations is slow: it can take hundreds of CPU clock cycles. So we have this intermediary layer named the cache: it is made of a relatively small amount of fast memory (faster than RAM, slower than registers) that holds a subset of the program’s data. Data is loaded into the cache from memory on demand when requested by the CPU, and the unit of transfer between memory and the cache is a cache line, generally 64 contiguous bytes, to exploit the principle of locality. So, to get the best performance possible for a program – and this is the goal in HPC – it is important to fit as much as possible of the program’s data in the cache.

Cache-unfriendly Program Example

Let’s discuss an example. Consider the following program:

typedef struct {
    char c[60];
    int i;
    double d;
} my_struct;

#define N 100000000
my_struct array[N];

int main(int argc, char **argv) {
  struct timeval start, stop, res;
  my_struct s;

  gettimeofday(&start, NULL);

  /* Randomly access N elements */
  for(int i=0; i<N; i++)
      memcpy(&s, &array[rand()%N], sizeof(my_struct));

  gettimeofday(&stop, NULL);
  timersub(&stop, &start, &res);
  printf("%ld.%06ld\n", res.tv_sec, res.tv_usec);

  return 0;
}

This program accesses a large array of data structures. The data structure contains a string member, an int member, and a double member. In a relatively long loop, the program uses memcpy to read a given element from the array at a random index. We use gettimeofday to measure the execution time of the loop. This program is extremely memory intensive, with not much computation: it is memory-bound by the memory copy operations.

It turns out that this program is not very cache-friendly. If we look at the size of one element of the array, that is, sizeof(my_struct), we can see that it’s 60 + 4 + 8 = 72 bytes. This is slightly larger than a cache line, which is 64 bytes, and the array is likely laid out in memory as follows:

So most calls to memcpy in the program’s inner loop will require 2 cache lines to be fetched from memory into the cache.

Fitting Data into the Cache

We can fix that issue by updating the structure and array definitions as follows:

typedef struct {
    char c[52]; // down from 60, we have 52 + 4 + 8 == 64 bytes i.e. a cache line
    int i;
    double d;
} my_struct;

// force alignment of the array base address:
my_struct array[N] __attribute__ ((aligned(64)));

We reduce the size of the structure to be equal to that of a cache line. More precisely, we reduce the size of the string so that the size of one instance of the data structure is 64 bytes. Then we use the special keyword __attribute__ to make sure that the array is aligned to a cache line. In effect, this ensures that each element of the array is fully contained within a cache line:

On the computer on which this code was tested, this effectively speeds up the program by about 25%:

Such optimisations are possible in C because the language gives the programmer a large degree of control over the program’s memory layout; in other words, one can control the placement and sizes of data structures in memory.