###Projet d'informatique

Remarques:

• Pour évaluer l'égalité entre deux float, on ne peut pas utiliser ==. Ainsi on compare la valeur absolue de la différence avec un epsilon que l'on fixe (fixé au pas entre deux floats). Ainsi on teste:

fabs(U[i]-val) < EPSILON
```;

<a name="q1"></a>
## Question 1
On peut utiliser la routine block_find pour écrire une routine multi-threads en découpant le tableau en blocs.

Chaque bloc sera analysé par un thread différent qui le parcourt. 

Par exemple avec un tableau contenant 10 floats, si on veut utiliser deux threads on va découper le tableau en deux blocs (pas la peine d'en faire plus, le programme n'ira pas plus vite avec deux threads et plus de deux blocs).

* Le premier thread va chercher entre les indices 0 et 4. 
* Le second thread va chercher entre les indices 5 et 9. 

Ainsi on fait une recherche multi-threadée. 

<a name="q2"></a>
## Question 2

Une manière simple d'utiliser la routine cyclic_find telle qu'elle a été présentée est que chaque thread utilise le même pas (i_step) et que le tableau passé en argument à la méthode change. 

En effet, si l'on considère que l'on va utiliser deux threads, l'un va exécuter la méthode 

cyclic_find(p, 2, n-1);

 en considérant que p est de taille n, tandis que le second va exécuter la méthode 

cyclic_find(p+1, 2, n-1-1);

Ainsi, on exécute la méthode cyclic_find avec le même pas mais une fois sur le tableau p, l'autre fois sur le tableau p+1 (donc le tableau commençant à la seconde case de p). 

<a name="q3"></a>
## Question 3

A première vue, je ne vois pas ce qui permettrai de dire qu'un des deux programmes est plus rapide que le second, puisqu'ils vont faire le même nombre d'opérations, et que l'espérance de trouver la bonne valeur à la prochaine itération pour un thread est la même dans les deux cas. 

Une chose pourrait donner un avantage à la méthode par blocs est la performance des accès mémoire. En effet, dans la méthode par blocs, l'espace mémoire utilisé par un thread est contigu, tandis que dans la méthode cyclique, les deux espaces mémoire utilisés par les threads s'enchevètrent. 

<a name="q4"></a>
## Question 4

Afin de stopper les autres threads lorsque l'un d'entre eux a trouvé une valeur (cela marche car on recherche une seule valeur et non toutes, et que l'on ne recherche que la première), on peut utiliser une variable statique (un booleen) que l'on initialise à 0, et que le premier thread qui trouve la valeur recherchée change à 1.

### Cas block_find

a. Voyons la structure de données utilisée dans le code pour ce cas : 

```C
struct thread_data{
  unsigned int thread_id; //permet de désigner le thread de manière unique
  float *p; //le pointeur vers le tableau de données utilisée par le thread
  int i_start; // l'indice du tableau auquel va démarrer la recherche
  int i_end; // l'indice du tableau où l'on s'arrête
  float val; // la valeur recherchée
};

Remarque : On aurait pu passer un pointeur vers la première case d'un sous-tableau que doit explorer le thread (ainsi on se passerait de i_start), et i_end serait en fait la longueur d'un bloc

b. Dans ce cas on a assez naturellement (On considère un tableau de taille n, pour NB_THREAD threads) :

i_start = thread_id*(n/NB_THREADS);
i_end = (thread_id+1)*(n/NB_THREADS)-1;

c. Le programme complet pour le cas par blocs est dans le fichier block.c.

Cas cyclic_find

a. Voyons la structure de données utilisée dans le code pour ce cas :

struct thread_data{
  unsigned int thread_id; //permet de désigner le thread de manière unique
  float *p; //le pointeur vers le tableau de données utilisée par le thread
  int i_step;  // Le pas 
  float val; // La valeur recherchée
};

b. Dans ce cas, on a i_end = n-1-thread_id pour tous les threads et ```i_step = NB_THREAD````

c. Le programme complet pour le cas cyclique figure dans le fichier cyclic.c et est complètement documenté.