Le but de cet exercice est de vous montrer comment paralléliser l'exploration d'un arbre. Pour cela, on implémentera un algorithme séquentiel avant de comparer différentes méthodes de parallélisation. Nous utiliserons les bibliothèques rand pour générer des chaines de caractères aléatoires, rayon pour du parallélisme avec work-stealing et crossbeam pour du parallélisme avec threads classiques. Vous pouvez donc ajouter les lignes suivantes à votre fichier Cargo.toml.

crossbeam = "0.4"
rand = "0.5"
rayon = "1.0"

On considère des arbres binaires dont les feuilles sont étiquetées par des chaînes de caractères. En pratique, cela donne le type ci-dessous. On remarquera que les fils d'un nœud sont boxés. Cela est obligatoire pour les types récursifs qui n'auraient sinon pas une taille fixe.

# #![allow(unused_variables)]
#fn main() {
pub enum Tree {
    Node(Box<Tree>, Box<Tree>),
    Leaf(String),
}
#}

Question 1. Écrivez une fonction count_ab_seq qui compte le nombre feuilles contenant le sous mot "ab". Vous testerez votre fonction sur de petits exemples d'arbres.

On veux tester notre code sur des arbres équilibrés de différentes façon, pour voire comment les différentes méthodes de parallélisation se comportent dans chaque cas. Pour cela, on donne une fonction gen_tree qui génère un arbre binaire déséquilibré vers la droite d'un facteur balance. Si balance = 1, l'arbre est équilibré.

# #![allow(unused_variables)]
#fn main() {
use rand::{XorShiftRng, Rng};

/// Génère un arbre avec `n` feuilles tel que chaque sous-arbre ayant plus de `balance` feuilles
/// contiennent `balance` fois plus de feuilles dans son fils droit que gauche.
pub fn gen_tree(n: usize, balance: usize, rng: &mut XorShiftRng) -> Tree {
    match n {
        0 => panic!(),
        1 => Tree::Leaf(rng.gen_ascii_chars().take(500).collect()),
        n if n <= balance => gen_tree(n, 1, rng),
        n => {
            let lhs = gen_tree(n/(balance+1), balance, rng);
            let rhs = gen_tree(n-n/(balance+1), balance, rng);
            Tree::Node(Box::new(lhs), Box::new(rhs))
        },
    }
}

/// Example de génération d'un arbre de 100 000 feuilles, déséquilibré d'un facteur 8.
let tree = gen_tree(100_000, 8, &mut rand::weak_rng());
#}

Question 2. Écrivez des benchmarks pour la fonction count_ab_seq sur:

• un arbre équilibré de 100 000 feuilles,
• un arbre déséquilibré de 100 000 feuilles et
• un arbre de 100 feuilles.

Afin d'utiliser les mêmes arbres pour tous les benchmarks, vous les déclarerez comme des variables statiques en utilisant la bibliothèque lazy static.

On veux maintenant paralléliser notre code. Une première solution naïve est d'explorer les sous-arbres de chaque nœud en parallèle en créant un thread par fils.

Question 3. Écrivez un version parallèle count_ab_heavy_par de la fonction count_ab_seq qui créé un thread pour chaque fils de chaque nœud. Pour créer les threads, vous utiliserez la bibliothèque crossbeam et notamment la fonction scope et la méthode spawn. Nous vous invitons à lire attentivement la documentation de cette méthode pour comprendre pourquoi elle est préférable, dans notre cas, au spawn de la bibliothèque standard.

Question 4. Comparez la performance de count_ab_heavy_par à count_ab_seq sur l'arbre de 100 feuilles. Que se passe-t-il si on lance count_ab_heavy_par sur un arbre de 100 000 feuilles ?

On essaye maintenant de réduire la perte de performance infligée par la création de trop de threads. Pour cela, on ne vas générer des threads que jusqu'à une profondeur fixée.

Question 5. Écrivez une fonction count_ab_fixed_par qui se comporte comme count_ab_heavy_par jusqu'à une profondeur donnée (par exemple via un argument) puis comme count_ab_seq.

Question 6. Mesurer la performance de count_ab_fixed_par sur un arbre équilibré et un arbre déséquilibré. Comment expliquer la différence de performance par rapport à count_ab_heavy_par ? Comment expliquer la différence de performance entre les arbres équilibrés et déséquilibrés ?

On va maintenant comparer les deux méthodes précédentes à une parallélisation utilisant du work-stealing. Pour cela, on utilisera la fonction join de rayon.

Question 7. Parallélisez la fonction count_ab_seq en utilisant rayon::join. Comparez aux autres méthodes de parallélisation et expliquez les différences de performance.