Exercices de parallélismes
==========================

Min/Max
-------

Écrivez une fonction qui calcule le plus petit *et* le plus grand élément d'un
tableau de nombres *flottants* passez en paramètres.

.. code-block:: c

    #include <stdlib.h>
    #include <stdio.h>
    #include <limits.h>
    #include <sys/time.h>

    static void minmax(float const* start, float const* stop, float* min, float* max) {
      // giveme giveme a man fmin
    }

    int main(int argc, char**argv) {
        if(argc != 2) return 1;
        long long int n = atoll(argv[1]);
        float* data = malloc(n * sizeof(*data));
        for(int i = 0; i < n; ++i)
            data[i] = (unsigned)i * (UINT_MAX / 3); // pourquoi ce cast?

        struct timeval start, stop;
        float min, max;
        gettimeofday(&start, NULL);
        minmax(data, data +n, &min, &max);
        gettimeofday(&stop, NULL);
        printf("%f - %f\n", min, max);
        printf("%lf ms\n", (stop.tv_sec - start.tv_sec) * 1000. + (stop.tv_usec - start.tv_usec) / 1000.);
        return 0;
    }

Inspectez le code généré : utilise-t-il des instructions vectorielles ? Si non,
en vous basant sur le jeu d'instruction disponible sur votre machine (``cat
/proc/cpuinfo``), l'[aide en
ligne](https://software.intel.com/sites/landingpage/IntrinsicsGuide/) et votre
cervelet droit, implémentez en une!


Lock (Lamora) less Data structure
=================================

Commencer avec une structure sur un tableau de taille fixe anec just add / sub

Le programme suivant implémente une structure de donnée qui n'est pas *thread-safe*.

.. code-block:: c

    #include <stdlib.h>
    #include <stdio.h>
    #include <assert.h>

    typedef struct list {
      struct list* next;
      int val;
    } * list_t;

    list_t const empty_list = NULL;

    list_t make_list(int val) {
      list_t l = malloc(sizeof(*l));
      l->val = val;
      l->next = empty_list;
      return l;
    }

    void list_push_front(list_t *self, int val) {
      list_t res = make_list(val);
      res->next = *self;
      *self = res;
    }

    int list_pop_front(list_t* self) {
      assert(*self && "pop from empty list o_O");
      int val = (*self)->val;
      list_t next = (*self)->next;
      free(*self);
      *self = next;
      return val;
    }

    int list_front(list_t self) {
      assert(self && "front from empty list O_o");
      return self->val;
    }

    size_t list_size(list_t self) {
      size_t n = 0;
      while(self) {
        n += 1;
        self = self->next;
      }
      return n;
    }

    static size_t process(list_t *self, int add_count, int rm_count) {
      while(add_count--)
        list_push_front(self, add_count);
      while(rm_count--)
        list_pop_front(self);
      return list_size(*self);
    }

    int main(int argc, char** argv) {
      if(argc != 3) return 1;

      int add_count = atoi(argv[1]);
      int rm_count = atoi(argv[2]);
      list_t curr = empty_list;
      size_t final_size = process(&curr, add_count, rm_count);
      printf("%zd\n", final_size);
      return 0;

    }

Modifiez le en utilisant des [opérations
atomiques](http://en.cppreference.com/w/c/language/atomic) afin que la
structure soit *thread-safe*. Pour tester l'ensemble, vous pourrez utiliser un
une région parallèle OpenMP pour faire plusieurs appels concurents à ``process``.

Extraction de pages
===================

Que fait le script suivant ?

.. code-block::sh

    while read line
    do
        wget -O - "$line"
    done 2>/dev/null | grep -E -o 'href="http://[^"]*"' | sed -r 's/href="(.*)"/\1/'

Il est amusant (si si) de constater que la sortie peut être envoyer sur l'entrée. En procédant ainsi une fois, combien de pages aura-t-on visité ?

Comment accélérer ce traitement en utilisant l'opérateur ``&`` et en se synchronisant avec la commande ``wait`` du shell ?
Combien de processus sont alors lancés ? Utilisez ``xargs -l1 -P`` pour influer sur l'ordonnacement.


Tri parallèle
-------------

En réutilisant les fonctions ``std::sort``, ``std::inplace_merge`` et à l'aide de directives OpenMP, écrivez
une version parallèles d'un algorithme de tri de nombres entiers.

Dans un premier temps, vous pourrez paralléliser uniquement le tri, avec un
``merge`` séquentiel. Motivez l'utilisation d'un seuil à partir duquel il
faudrait basculer sur l'algorithme séquentiel.  Quelle est alors la complexité
de l'algo parallèle ?  Essayez ensuite de paralléliser le ``merge``.

Comparez vos résultats en utilisant des tableaux d'entiers de taille
différente. Comment évolue le nombre d'octets traités par seconde ?


.. code-block:: c++

    #include <algorithm>
    #include <iostream>
    #include <limits>
    #include <sys/time.h>

    int main(int argc, char**argv) {
        if(argc != 2) return 1;
        int n = std::stoi(argv[1]);
        double *data = new double [n];
        for(int i = 0; i < n; ++i)
            data[i] = (double)i * (std::numeric_limits<int>::max() / 3);

        struct timeval start, stop;
        gettimeofday(&start, NULL);
        std::sort(data, data + n);
        gettimeofday(&stop, NULL);
        volatile __attribute__((unused)) double anchor = data[n/2]; // why that?
        std::cout << ((stop.tv_sec - start.tv_sec) * 1000. + (stop.tv_usec - start.tv_usec) / 1000.) << " ms\n" ;
        delete [] data;
        return 0;
    }