Models & Tools for Parallelism

Home| Course

Foreword

The following exercises needs for you to access a Unix system. A Linux operating system would be better (because I didn't try these exercises on Solaris) but probably not mandatory.

1. C versus C++

1. Compile the following piece of code and stop gcc at the assembly code stage:

   #include <stdio.h>
   int main() {
     printf("Hello World !\n");
     return 0;
   }
   

2. Compile the following piece of code and stop g++ at the assembly code stage:

   #include <iostream>
   using namespace std;
   int main() {
     cout << "Hello World !" << endl;
     return 0;
   }
   

3. Look at the differences of the two assembly codes. How can you explain these differences ? Based on these remarks, tell when it make sense to use C and when to use C++.

2. Code Optimization

1. What optimizations can we perform on the following piece of code ?

   int i,j;
   double array[width*height];
    for(j=0; j < height; j++) {
     for(i=0; i < width; i++) {
       foo(i,j, array[j*width+i];
      }
    }
   

2. Does gcc do this optimization automatically ? At what optimization level (0, 1, 2 or 3) ?

3. Loop Unrolling

1. Compare (with gprof) the two way of doing a fixed number of loops (rolled/unrolled). Try with longer loops and evaluate the impact of the two methods on the performances depending on the number of loops.

   // Normal for-loop
   for(int i=0; i < 3; i++) { array[n+i] = i; }
   // unrolled version
   int i = 0;
   array[+i] = i;
   i++;
   array[n+i] = i;
   i++;
   array[n+i] = i;
   

2. Compare (with gprof) the two way of doing a fixed number of loops (rolled/unrolled). Try with longer loops and evaluate the impact of the two methods on the performances depending on the number of loops.

   // Unbounded loop
   for(int i=0; i < n; i++) { *dest++ = *source++; }
   // unrolled version
   // knowing n ist always a multiple of four
   for(int i=0; i < n; i+=4) {
     *dest++ = *source++;
     *dest++ = *source++;
     *dest++ = *source++;
     *dest++ = *source++;
   }
   

3. Try to see what happens when the options -funroll-all-loops or -funroll-loops are specified when compiling or not on the rolled/unrolled programs you wrote.

4. Arithmetic on Default Types

Try to compare (with gprof) the performance of addition, soustraction, multiplications (and other arithmetic operations) on differents default data types (byte, int, float, double, ...).

5. Array Versus Linked-list

Analyze the difference of perfomance to browse through an array and a linked-list. Make some statistics depending on the size of the array/linked-list. Try to evaluate how fragmentation of the data over the memory affect the performances of accessing to the data

6. Dynamic Memory Allocation

Evaluate what is the cost of using dynamic memory allocation (malloc()).

1. Compare a method allocating the whole thing at once to a method adding small chunks one after one.
2. Tell what are the performances depending on: the size of the whole chunk, the size of each small allocation.