:: Enseignements :: ESIPE :: E4INFO :: 2008-2009 :: Java Réseau I - Concurrence et E/S ::

Examen de Septembre de concurrence sur machine (2h)

Exercice 1 - Map-Reduce

On souhaite réduire le temps d'exécution d'un ensemble d'algorithmes en découpant un problème basé sur des tableaux en déroulant en parallèle l'algorithme sur des morceaux du tableau puis en regroupant les résultats obtenus en un seul.

On se propose pour cela d'utiliser les classes suivantes :

     interface TaskFactory<V,T> {
       Task<V,T> createTask();
     }
     interface Task<V,T> {
       V process(T[] array, int offset, int length);
     }
     interface Reducer<V,R> {
       R reduce(V value, R oldResult);
     }

     public class MapReduce {
       public MapReduce(int maxThread) {
         ... // à compléter
       }
       public <R,V,T> R solve(T[] array, TaskFactory<? extends V,T> taskFactory,
                                    Reducer<? super V,R> reducer, R initValue) {
         ... // à compléter
       }
     }

La méthode solve, prend le tableau en paramètre, crée un certain nombre de tâches en utilisant le taskFactory. Chaque tâche est exécutée par une thread en parallèle, pour cela chaque thread appelle la méthode process avec la partie du tableau correspondant à chaque tâche. Par exemple, s'il y a 3 threads, chaque thread executera process sur un tiers du tableau. Puis le resultat de chaque process est collecté par la méthode reduce du Reducer. Lors du premier appel au reducer, oldResult correspond à initValue ; après à chaque appel, l'ancienne valeur de retour de l'appel à la méthode reduce est uilisé en tant que oldResult. L'argument value correspond à la valeur de retour de la méthode process.

En supposant que la classe MapReduce existe. Donner un code permettant de calculer le maximum d'un tableau de Double en utilisant la méthode solve.
Implantation la classe MapReduce sachant:
- que l'on crée autant de threads que maxThread
- que l'on demande à chaque thread d'exécuter sa tâche sur une partie du tableau (il y a maxThread parties).
- > que pour récupérer le résultat final, on combine les résultats intermédiaires résultant du calcul de chaque thread en appliquant le Reducer sur chaque résultats partiels.
Pour effectuer la synchronisation entre les threads et la méthode principale vous utiliserez Object.wait/notify ou Condition.await/signal.
Donner une nouvelle implantation, la classe MapReduce2 utilisant un ExecutorService ainsi que des futures.
Utiliser la classe MapReducer2 pour calculer le nombre de ligne (le nombre d' '\n') d'un fichier par 5 threads en concurrence.