• Programmation parallèle
  • 17/09: Cours d'Albert Cohen, TD (1h30 + 2h)
  • 18/09: Cours, TD
  • 24/09: Cours, TD
  • 25/09: Cours (3h)
  • 01/10: TD (4h)

• Programmation réactive
  • 08/10: Cours de Marc Pouzet, TD
  • 09/10: Cours, TD
  • 15/10: Cours de Louis Mandel sur RML, TD
  • 16/10: Cours de Louis Mandel sur RML, TD
  • 22/10: TD (4h)
  • 05/11: Cours, TD
  • 06/11: Cours, TD (code)

• Introduction à Rust présentée au meeting du projet Rust Belt en juin 2017.

• Cours CIS 198 à U. Penn et notamment les cours couvrant ownership, closures, et concurrency.

• Introduction à Rayon

• BSP: transparents sur le work-stealing en environnement hétérogène

• BSP: présentation rapide de map-reduce selon Google

• Rustlings petits exercices pour la prise en main du langage.

• Rust by example

• Rayon parallélisme de données et de tâches avec "vol de travail" (work-stealing).

• Tokio application des futures et flots (streams), et de la boucle d'évènements (event loop) pour des entrées sorties asynchrones (asynchronous I/O).

Le but de ce TD est de se familiariser avec Rust et de démontrer l'utilité du parallélisme de données en parallélisant une simulation de la diffusion de la chaleur en 2D.

Vous pouvez utiliser le playground pour effectuer tous les exercices.

Commencez par parcourir la liste des sections de l'excellent rust by example et lisez les sections avec lesquelles vous n'êtes pas à l'aise (il est fortement recommandé de faire les exercices du premier chapitre si vous n'avez jamais fait de Rust). Vous pouvez ensuite passer aux exercices. Gardez rust by example ainsi que le livre Rust sous la main en tant que référence.

Ces exercices sont construits comme des "puzzles" donnant du code Rust presque correct, mais qui ne compile pas. Le but de chaque exercice est de faire accepter le code au compilateur.

Question 1.

mod printer {
    fn print_test_page() {
        println!("A bunch of stuff no one looks at anyways.");
    }
}

fn main() {
    printer::print_test_page();
}

Question 2.

mod runtime {
    use parallel::RUNTIME as PARALLEL;
    use sequential::RUNTIME as SEQUENTIAL;

    mod sequential {
        pub const RUNTIME: &'static str = "sequential";
    }

    mod parallel {
        pub const RUNTIME: &'static str = "parallel";
    }
}

fn main() {
    println!(
        "Available runtimes: {}, {}",
        runtime::SEQUENTIAL,
        runtime::PARALLEL
    );
}

Question 1.

fn main() {
    quantity = 100;
    println!("Initial quantity: {}", quantity);
}

Question 2.

fn main() {
    let quantity;
    if quantity <= 50 {
        println!("We should restock.");
    }
}

Question 3.

fn main() {
    let quantity = 100;
    println!("Initial quantity: {}", quantity);
    quantity -= 1;
    println!("One item sold; new quantity: {}", quantity);
}

Question 1.

fn main() {
    my_main();
}

Question 2.

fn main() {
    my_main(3);
}

fn my_main(num_iters) {
    for i in 0..num_iters {
        println!("Iteration #{}", i + 1);
    }
}

Question 3.

Trois erreurs à la fois. Je n'étais vraiment pas réveillé en écrivant ce code :)

fn main() {
    println!("Result is {}", my_main());
}

fn my_main(num_iters: u32) -> {
    (0..num_iters).fold(0, |x, y| x + y);
}

Question 1.

trait MyTrait {}

fn use_trait(_: MyTrait) {}

fn main() {}

Question 2.

trait MyTrait {}

impl MyTrait for i32 {}

fn use_impl_box<T: MyTrait>(_: &T) {}

fn use_dyn_box(_: &dyn MyTrait) {}

fn main() {
    let x: i32 = 3;
    let i32_x: &i32 = &x;
    let dyn_x: &dyn MyTrait = &x;
    use_impl_box(i32_x);
    use_impl_box(dyn_x);
    use_dyn_box(i32_x);
    use_dyn_box(dyn_x);
}

Question 1.

fn flatten_ref<'a, 'b>(x: &'a &'b mut u32) -> &'b mut u32 {
    x
}

fn main() {}

You can use chapters 10.3 and 19.2 as a reference for these exercices.

As a motivating example for this section, let us consider the idea of a task scheduler. The user can write tasks (units of computation) which should be run, and each task can schedule additional tasks to run after it has completed.

You will have to write a parallel runtime for such a scheduler in the project -- but for now, let us consider a simpler, sequential implementation to illustrate some lifetime issues. Below is a simple implementation using a queue of tasks backed by a vector of references. The code is correct, but there are some lifetime issues which Rust is complaining about. Explain why, and make the code compile using only lifetime annotations.

/// A task represents an unit of computation.
trait TaskMut: 'static {
    /// Execute the task.  The task can use the scheduler to mark additional tasks as needing to be
    /// run.
    fn execute_mut(&mut self, scheduler: &mut dyn Scheduler);
}

/// A scheduler object allowing to register tasks to be executed asynchronously.
trait Scheduler {
    /// Schedule a new task to be executed.  The `Scheduler` should not execute the task
    /// immediately; rather, the task should be stored in an auxiliary data structure and executed
    /// at a later time.  The caller should ensure that any prerequisites for the task's execution
    /// are met.
    fn schedule_mut(&mut self, task: &mut dyn TaskMut);
}

/// A basic runtime.  It maintains ready vector of tasks to schedule, and executes them
/// sequentially.  When executing, tasks can schedule additional tasks to run later.
///
/// The intended use case is that tasks should be pre-allocated before being
/// passed to the `Runtime`, which doesn't care about memory management at all.
/// Hence, the `Runtime` type takes a lifetime `'r` as argument, which is a
/// lower bound on the lifetime of the tasks.
struct Runtime<'r> {
    /// Ready vector of tasks to execute.
    ready: Vec<&'r mut dyn TaskMut>,
}

impl<'r> Runtime<'r> {
    /// Create a new Runtime from a vector of tasks references.
    fn new(ready: Vec<&'r mut dyn TaskMut>) -> Self {
        Runtime { ready }
    }

    /// Execute tasks until none are left.
    fn execute(&mut self) {
        while let Some(task) = self.ready.pop() {
            task.execute_mut(self)
        }
    }
}


// Implement the Scheduler trait for the Runtime.  We want tasks to be able to register additional
// tasks when being run.
impl<'r> Scheduler for Runtime<'r> {
    /// Schedule a task by registering it into the runtime's `ready` queue.
    fn schedule_mut(&mut self, task: &mut dyn TaskMut) {
        self.ready.push(task)
    }
}

fn main() {}

Hint: we should only be able to schedule tasks which outlive the scheduler -- otherwise we could end up with dangling pointers when we get to executing them. The following code must be prevented somehow:

struct NoOp;

impl TaskMut for NoOp {
    fn execute_mut(&mut self, _: &mut dyn Scheduler) {
        // This is called "NoOp". What did you expect?
    }
}

fn main() {
    let mut runtime = Runtime::new(Vec::new());

    {
        let mut stack_task = NoOp;
        runtime.schedule(&mut stack_task);
    }

    // The runtime cannot still have a reference to `stack_print` here!
    runtime.execute()
}

We are using references in the runtime because we want to be able to run our graph of tasks multiple times, possibly in different runtimes (for instance, the tasks could implement one step of a physical simulation - or video game loop). Hence the following code, which takes a vector of owned tasks and runs them using a local scheduler, should be allowed:

# #![allow(unused_variables)]
#fn main() {
fn execute(tasks: &mut Vec<Box<dyn TaskMut>>) {
    let mut runtime = Runtime::new(tasks.iter_mut().map(Box::as_mut).collect());
    runtime.execute();
}
#}

Does your solution to question 1 allow this use case? If not, propose another solution which does not prevent re-executing the tasks with a different scheduler.

Hint: tasks should not be tied to a particular scheduler lifetime. They need to be usable with any lifetime, as long as we have a sufficiently long-lived reference.

We added a constraint that the TaskMut trait must have a 'static lifetime, i.e. should not contain any reference. Alter the lifetime annotations to allow tasks to contain references.

Hint: tasks should still not be tied to a particular lifetime. Remove the 'static bound and let the compiler guide you.

We want tasks to be able to schedule other tasks, which is currently not possible, as evidenced by the following Loop task which doesn't typecheck:

# #![allow(unused_variables)]
#fn main() {
struct Loop;

impl TaskMut for Loop {
    fn execute_mut<'r>(&mut self, scheduler: &mut dyn Scheduler<'r>) {
        scheduler.schedule_mut(self)
    }
}
#}

Can you find a way to make it work with only lifetime annotations? Is it possible to add an inner task to the Loop as a body (so that the definition becomes struct Loop<T> { body: T }), calling execute_mut on the body each time the Loop is scheduled (in addition re-scheduling the Loop)?

Let's try to find a formulation where we can write a loop. Remove the extra lifetime from the TaskMut trait so that the signature of execute_mut is fn execute_mut<'r>(&mut self, scheduler: &mut dyn Scheduler<'r> again.

We now define the following extra traits:

# #![allow(unused_variables)]
#fn main() {
trait Task {
    fn execute<'r>(&self, scheduler: &mut dyn Scheduler<'r>);
}

trait TaskBox {
    fn execute_box<'r>(self: Box<Self>, scheduler: &mut dyn Scheduler<'r>);
}
#}

and add the corresponding schedule(&mut self, node: &'r dyn Task) and schedule_box(&mut self, node: Box<dyn TaskBox + 'r>) methods on the Scheduler trait. Which of the following impls can you write?

• impl<T: Task> Task for Loop<T>
• impl<T: Task> TaskMut for Loop<T>
• impl<T: TaskMut> TaskMut for Loop<T>
• impl<T: Task> TaskBox for Loop<T>
• impl<T: TaskMut> TaskBox for Loop<T>
• impl<T: TaskBox> TaskBox for Loop<T>

What is the difference between the TaskBox trait and the TaskMut with a &'r mut self parameter from the previous question?

Let us add an explicit runtime reference to the Task trait:

# #![allow(unused_variables)]
#fn main() {
trait Task {
    fn execute<'r>(&'r self, scheduler: &mut dyn Scheduler<'r>);
}
#}

Can you now write an impl<T: Task> Task for Loop<T>? Can you explain why it works for Task but not TaskMut?

Hint: for implementing a loop, we need two things: tasks which are able to re-schedule themselves, and tasks which are able to schedule repeatedly inner tasks. Is it possible to encode those two capabilities in the same trait taking mutable references? What about immutable references?

In order to be able to place a reference inside a structure, we need to ensure that the reference outlives the structure. In particular, the task reference in schedule_mut must outlive the scheduler instance. In order to express this constraint, we need to add a lifetime parameter to the Scheduler trait:

# #![allow(unused_variables)]
#fn main() {
/// The lifetime parameter 'a indicates the scheduler's lifetime.  Only tasks
/// which live longer than this lifetime can be scheduled.
trait Scheduler<'a>: 'a {
    /// By taking a `&'a mut` reference to the task, we ensure that it can be
    /// stored inside the scheduler.
    fn schedule_mut(&mut self, task: &'a mut dyn TaskMut);
}

impl<'r> Scheduler<'r> for Runtime<'r> {
    /// Schedule a task by registering it into the runtime's `ready` queue.
    fn schedule_mut(&mut self, task: &'r mut dyn TaskMut) {
        self.ready.push(task)
    }
}
#}

Don't forget to add the lifetime in the TaskMut trait definition as well:

# #![allow(unused_variables)]
#fn main() {
trait TaskMut: 'static {
    fn execute_mut<'a>(&mut self, scheduler: &mut dyn Scheduler<'a>);
}
#}

The 'a parameter we added in the execute_mut function could have been added to the TaskMut trait directly instead. However, this would make the nodes usable with a single scheduler: we would like to avoid that if possible.

The trait definitions for this will still work; however the execute function from the previous question won't. We need to change it to the following:

# #![allow(unused_variables)]
#fn main() {
fn execute<'r>(tasks: &'r mut Vec<Box<dyn TaskMut + 'r>>) {
    let mut runtime = Runtime::new(tasks.iter_mut().map(Box::as_mut).collect());
    runtime.execute();
}
#}

This is required because Box<dyn TaskMut> is implicitely converted to Box<dyn TaskMut + 'static>, i.e. trait objects as generic parameters contain an implicit static lifetime. This is because we could implement TaskMut for a type which contain a lifetime, such as &'a i32.

The compiler error about this is relatively explicit: we take an &mut reference to self, but then we try to schedule it with a &'r mut reference. Since the 'r lifetime outlives the local function lifetime, we can't do this (see also the flatten_ref question in the first part)! One solution is to simply use a &'r mut lifetime when calling execute_mut:

# #![allow(unused_variables)]
#fn main() {
trait TaskMut {
    fn execute_mut<'r>(&'r mut self, scheduler: &mut dyn Scheduler<'r>);
}

struct Loop;

impl TaskMut for Loop {
    fn execute_mut<'r>(&'r mut self, scheduler: &mut dyn Scheduler<'r>) {
        scheduler.schedule_mut(self)
    }
}
#}

However, we can't use this to execute a loop's body and re-schedule the loop itself. Indeed, the API allows any node to re-schedule itself -- and in particular, the body could do so! In the following scenario:

• Loop executes
  • Body executes and re-schedules itself: there is an &'r mut to the body in the scheduler
• Loop re-schedules ifself: there is an &'r mut to the loop in the scheduler... but we can get an &'r mut to the body from that!

we can create two mutable references to the loop body at once, so there is no way we will fix that issue with lifetime annotations.

The only valid implementations are:

# #![allow(unused_variables)]
#fn main() {
impl<T: Task> TaskBox for Loop<T> {
    fn execute_box<'r>(self: Box<Self>, scheduler: &mut Scheduler<'r>) {
        self.body.execute(scheduler);
        scheduler.schedule_box(self);
    }
}

impl<T: TaskMut> TaskBox for Loop<T> {
    fn execute_box<'r>(mut self: Box<Self>, scheduler: &mut Scheduler<'r>) {
        self.body.execute_mut(scheduler);
        scheduler.schedule_box(self);
    }
}
#}

Conceptually, there is no difference between the TaskBox trait and the TaskMut trait with &'r mut arguments. In general, Box<T> and &'r mut T restrict what we can do with T in the same way; the only difference is that when the Box<T> goes out of scope the memory will be freed but nothing will happen when &'r mut T goes out of scope.

If we allow &'r arguments, we can also write:

# #![allow(unused_variables)]
#fn main() {
impl<T: Task> Task for Loop<T> {
    fn execute<'r>(&'r self, scheduler: &mut Scheduler<'r>) {
        self.body.execute(scheduler);
        scheduler.schedule(self);
    }
}
#}

This is because by using an immutable reference we solve the issue described in the previous question: immutable references can be cloned, and it is not a problem to have multiple ones of them.

Le but de cet exercice est de simuler la propagation de la chaleur dans un matériau uniforme, en deux dimensions. Pour cela, on commencera par écrire une version séquentielle du calcul avant de le paralléliser.

Correction

La première étape est de créer un projet qui affiche un image dans un fenêtre. Pour cela, nous utiliserons les bibliothèques:

• piston_window pour afficher une fenêtre graphique,
• image pour créer une image à partir de la distribution de la température, et
• fps_counter pour compter le nombre d'images produites par seconde.

Créez un nouveau projet Rust (cargo init --bin) et éditez la section [dependencies] du ficher Cargo.toml pour dépendre de ces libraires.

[dependencies]
fps_counter = "1.0"
image = "0.15"
piston_window = "0.70"

On donne une fonction display qui affiche une image dans une fenêtre. Cette fonction prend en argument le titre de la fenêtre, sa largeur et sa hauteur ainsi qu'une fonction step calculant un pas de la simulation. La fonction step prend en argument une référence mutable vers l'image afficher dans la fenêtre et est chargée de la mettre à jours pour le pas suivant.

//! Simulation de l'équation de la chaleur.
extern crate fps_counter;
extern crate image;
extern crate piston_window;

use piston_window::*;

/// Ouvre une fenêtre pour afficher une image. L'image est mise à jour entre chaque
/// affichage en appelant la fonction `step`.
pub fn display<F>(title: &str, height: usize, width: usize, mut step: F)
        where F: FnMut(&mut image::RgbaImage) {
    // Création de la fenêtre.
    let glutin_window = WindowSettings::new(title, (width as u32, height as u32))
        .exit_on_esc(true)
        .resizable(false)
        .srgb(false) // Necessary due to issue #139 of piston_window.
        .build()
        .unwrap_or_else(|e| panic!("Failed to build window: {}", e));
    let mut window: PistonWindow = PistonWindow::new(OpenGL::V3_2, 0, glutin_window);
    // Création de l'image.
    let black_pixel = image::Rgba { data: [0, 0, 0, 255] };
    let mut img = image::RgbaImage::from_pixel(width as u32, height as u32, black_pixel);
    let tex_settings = TextureSettings::new();
    let mut tex_factory = window.factory.clone();
    // Création du conteur de FPS.
    let mut fps_counter = fps_counter::FPSCounter::new();
    let font = "assets/FiraMono-Regular.ttf";
    let glyph_settings = TextureSettings::new();
    let mut glyphs = Glyphs::new(font, window.factory.clone(), glyph_settings).unwrap();

    // Boucle de traitement des évenements.
    while let Some(e) = window.next() {
        window.draw_2d(&e, |c, g| {
            clear([0.0, 0.0, 0.0, 1.0], g);
            // Affichage d'un pas de calcul.
            step(&mut img);
            let tex = Texture::from_image(&mut tex_factory, &img, &tex_settings).unwrap();
            image(&tex, c.transform, g);
            // Affichage du compteur de fps.
            let fps = format!("{} fps", fps_counter.tick());
            let transform = c.transform.trans((width-100) as f64, 30.0);
            text([1.0, 1.0, 1.0, 1.0], 32, &fps, &mut glyphs, transform, g);
        });
        e.idle(|_| {
            fps_counter.tick();
            step(&mut img);
        });
    }
}

/// Hauteur de la carte de température.
const HEIGHT: usize = 600;
// Largeur de la carte de température.
const WIDTH: usize = 800;

fn main() {
    display("Propagation de la chaleur 2D", HEIGHT, WIDTH, |image| {
      // TODO: calculer un pas de simulation
    });
}

Pour pouvoir afficher le nombre d'image par seconde, nous avons besoin de fournir une police de caractères. Pour cela, créez un dossier assets/ à la racine du projet et copiez y le fichier de police Fira Mono (license).

Si vous compiler et exécutez le code, vous devriez maintenant voir une fenêtre noire avec un compteur d'image par seconde en haut à droite s'afficher. Le deuxième étape est maintenant de mettre à jours l'image avec la valeur de la température. La température est stockée dans un tableau de tableau de flotants (type Vec<Vec<f64>>). Afin de convertir la température en couleur, nous fournissons la fonctions map_color qui convertie un flotant entre -1 et 1 en composantes rouge, verte et bleue.

# #![allow(unused_variables)]
#fn main() {
/// Maps values between -1 and 1 to RGB colors.
fn map_color(value: f64) -> (u8, u8, u8) {
    // Express as HSL with S=1 and L=.5, and H between 0(red) and 4/6(blue).
    let h = f64::max(0.0, f64::min(1.0, (1.0-value) * 2.0/6.0));
    // Then convert to RGB.
    let x = 1.0 - (((h*6.0) % 2.0) - 1.0).abs();
    let (r, g, b) = if h < 1.0/6.0 {
        (1.0, x, 0.0)
    } else if h < 2.0/6.0 {
        (x, 1.0, 0.0)
    } else if h < 3.0/6.0 {
        (0.0, 1.0, x)
    } else {
        (0.0, x, 1.0)
    };
    ((r*255.0) as u8, (g*255.0) as u8 , (b*255.0) as u8)
}
#}

Pour exécuter votre code, utilisez cargo run --release. La commande cargo run exécute votre code en mode debug par défaut, qui sera trop lent pour ce TD.

Question 1. Écrivez une fonction temp_to_image qui prend en entrée une référence vers la matrice de température et une référence mutable vers l'image et qui modifie l'image pour représenter la température. L'image est représentée comme un tableau de bytes (type [u8]) de taille 4*HEIGHT*WIDTH où:

• la case 4 * (i * WIDTH + j) représente la composante rouge du pixel (i, j).
• la case 4 * (i * WIDTH + j) + 1 représente la composante verte du pixel (i, j).
• la case 4 * (i * WIDTH + j) + 2 représente la composante bleue du pixel (i, j).
• la case 4 * (i * WIDTH + j) + 3 représente la composante transparence du pixel (i, j), à laisser à 255 (opaque) dans notre cas.

Question 2. Pour vérifier que tout marche, on va maintenant afficher la distribution de température \(u(x, y, t)\):

\[u(x, y, t) = \sin \left( \frac{t+x+y}{2\pi} \right)\]

Modifiez la fonction main pour afficher cette distribution en utilisant la fonction temp_to_image. Vous utiliserez les constantes DT et DX définies comme suit pour représenter le pas temporel de calcul et l'espacement entre deux pixels. La constante \(\pi\) est définie en Rust par std::f64::consts::PI.

# #![allow(unused_variables)]
#fn main() {
/// Pas temporel de calcul.
const DT: f64 = 1.0e-4;
/// Pas dimentionel de calcul.
const DX: f64 = 1.0e-1;
#}

Vous devriez obtenir une image avec des bandes transversales qui se déplacent, comme dans l'image ci-dessous.

On va maintenant passer à la simulation de la diffusion de la chaleur. La propagation de la chaleur est définie par l'équation: \[\frac{\partial u}{\partial t} = K \left(\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2}\right) \] Ce qui donne, une fois discrétisé: \[ \begin{eqnarray} u(t+dt, x, y) = u(t, x, y) + \frac{K \times dt}{dx^2} &\Big[& u(t, x-dx, y) + u(t, x+dx, y) - 2 u(t, x, y) \\ &+& u(t, x, y-dx) + u(t, x, y+dx) - 2 u(t, x, y) \Big] \end{eqnarray} \]

Question 3. Écrire une fonction small_step qui calcule la nouvelle carte de température en fonction de l'ancienne. La constante K sera pour le moment fixée à 25. On réutilisera la distribution de la question 2 pour la valeur de la température aux bords.

# #![allow(unused_variables)]
#fn main() {
const K: f64 = 25.0;

fn small_step(old_temp: &Vec<Vec<f64>>, new_temp: &mut Vec<Vec<f64>>, time: f64) {
    // TODO: calculer new_temp en fonction de old_temp
}
#}

On ne peux pas afficher la carte de température à chaque pas de calcul car cela consommerait trop de ressources. À la place, on fait plusieurs appels à small_step dans chaque appel de la fonction step passée à display. Le nombre de petits pas de calcul sera défini par la constante SMALL_STEP.

# #![allow(unused_variables)]
#fn main() {
const SMALL_STEP: usize = 32;
#}

Question 4. Modifiez la fonction main pour simulez l'équation de la chaleur. On initialisera la carte de température à -1. Pour échanger les valeurs de l'ancienne de la nouvelle carte de température, vous pourrez utiliser la fonction std::mem::swap

Il est conseillé de fixer DT à \(10^{-4}\) pour que le pas temporel ne soit pas trop grand et que la simulation fonctionne. Vous pourrez ensuite jouer avec les différents paramètre pour voire comment évolue la distribution de la chaleur.

On va maintenant paralléliser les fonctions small_step et temp_to_image afin d'accélérer la simulation. Pour cela, nous utiliserons la bibliothèque rayon vue en cours. Il faut donc ajouter une dépendance à la version 0.8 de rayon dans le fichier Cargo.toml. Nous vous invitons fortement à consulter la documentation de rayon et notamment les pages sur les traits ParallelIterator et IndexedParallelIterator qui indiquent les opérations que l'on peux effectuer sur un itérateur parallèle et sur un itérateur parallèle indexé. On rappelle que pour utiliser rayon, il faut importer le prélude de rayon dans le contexte:

# #![allow(unused_variables)]
#fn main() {
use rayon::prelude::*;
#}

Question 5. Écrivez un version parallèle de small_step que vous nommerez small_step_par et modifiez la fonction main pour l'utiliser. Vérifiez que vous améliorez bien la vitesse de simulation.

Question 6. De même, parallélisez la fonction temp_to_image dans une nouvelle fonction temp_to_image_par.

On veux maintenant mesurer de façon précise le gain de performance apporté par le parallélisme. Pour cela, on va benchmarker la fonction small_step en isolation. Pour mesurer le temps d'exécution, on utilisera les fonctionnalités de benchmarking de Rust décrites ici.

Question 7. Calculez le facteur d'accélération des versions parallèles de small_step et de temp_to_image par rapport aux versions séquentielles.

Question 8 (exploratoire). On souhaite à présent optimiser la fonction small_step afin d'accélérer encore la simulation.

1. La première idée consiste à tirer parti de la localité temporelle du calcul, en effectuant un déroulage de boucle selon la deuxième dimension. Le compilateur pourra ainsi découvrir automatiquement que les valeurs lues sur le front droit du stencil viennent d'être calculées quelques instructions plus tôt, et éliminera ainsi quelques accès mémoire.

2. Une autre approche repose sur la vectorisation des instructions de calcul à travers plusieurs itérations de la première dimension. Le compilateur Rust reposant sur LLVM (http://llvm.org), un environnement très riche de compilation disposant d'une passe de vectorisation automatique, capable de regrouper plusieurs opérations ou accès mémoire consécutifs en une seule instruction dite vectorielle (ou SIMD) du processeur. On pourra tenter de déclencher cette vectorisation au prix d'une transformation de boucles appelée stripmining, effectuant le calcul par pas d'exactement 4 itérations (les instructions vectorielles sur processeurs x86 sont de taille 256 bits, soit 4 nombres à virgule flottante de 64 bits sur la plupart des processeurs récents). La configuration fine du compilateur L'analyse du code assembleur généré est nécessaire pour inspecter la réussite ou non de l'opération.

3. Une troisième voie consiste à explorer le partitionnement temporel du calcul, ou time tiling, et notamment les méthodes appelées overlapped tiling ou split tiling. Veuillez vous adresser aux enseignants pour explorer cette optimisation.

Le but de ce TD est d'utiliser le parallélisme de tâches. Pour cela on commencera par tester différentes techniques de parallélisation sur les arbres avant de se pencher vers l'exploration parallèle de graphes pour résoudre des labyrinthes.

Correction

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.

Le but de cet exercice est de résoudre des labyrinthes rapidement en utilisant du parallélisme de tâches. Plus précisément on cherche le chemin pour aller à n'importe quel point du labyrinthe.

En pratique, un labyrinthe sera représenté par un graphe de N nœuds, étiquetés de 0 à N-1. Le nœud 0 sera l'entrée. Le type du graphe sera déclaré comme ci-dessous.

# #![allow(unused_variables)]
#fn main() {
/// Un graphe orienté représenté par des listes d'adjacence. Le graphe peut contenir des
/// boucles d'une seule arête et peut avoir plusieurs arêtes entre les mêmes nœuds.
struct Graph {
    nodes: Vec<Vec<usize>>,
}

impl Graph {
    /// Créé un nouveau graphe sans arêtes.
    fn new(num_nodes: usize) -> Self {
        Graph {
            nodes: (0..num_nodes).map(|_| vec![]).collect()
        }
    }

    /// Retourne les voisins d'un nœud.
    fn neighbors(&self, node: usize) -> &[usize] { &self.nodes[node] }

    /// Retourne le nombre de nœuds dans le graphe.
    fn num_nodes(&self) -> usize { self.nodes.len() }

    /// Ajoute une arête au graphe.
    fn add_edge(&mut self, src: usize, dst: usize) {
        self.nodes[dst].push(src);
        self.nodes[src].push(dst);
    }
}
#}

Afin de benchmarker nos algorithmes, on utilisera la fonction ci-dessous pour générer des graphes aléatoires.

# #![allow(unused_variables)]
#fn main() {
/// Génère un graphe aléatoire avec `num_nodes` nœuds et density*num_nodes arêtes.
fn gen_graph(num_nodes: usize, density: f64) -> Graph {
    assert!(density >= 1.0);
    let mut graph = Graph::new(num_nodes);
    let mut rng = rand::weak_rng();
    // Generate a tree.
    for i in 1..num_nodes { graph.add_edge(i, rng.gen_range(0, i)); }
    // Add edges.
    for _ in 0..(num_nodes as f64 * (density-1.0)) as usize {
        graph.add_edge(rng.gen_range(0, num_nodes-1), rng.gen_range(0, num_nodes-1));
    }
    graph
}
#}

Question 1. Écrivez une fonction find_path qui trouve un chemin entre l'entrée et tous les points du graphe. Cette fonction retournera un tableau contenant le prédécesseur de chaque noeud sur le chemin qui le relie à l'entrée.

Attention: On demande pas forcément le plus court chemin.

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

• un graphe de 100 000 noeuds, avec une densité de 100 et
• un graphe de 100 000 noeuds, avec une densité de 10.

Question 3. Écrivez une version parallèle de la fonction find_path. Testez votre implémentation sur les différents graphes de benchmarks. Si votre version parallèle n'accélère pas beaucoup le calcul (ou le ralenti), essayez d'expliquer ce phénomène et d'améliorer votre code en conséquent.

Pour paralléliser votre code, vous pourrez utiliser (on non) certain des objets ou fonctions ci-dessous:

• les verrous,
• les types atomiques,
• la fonction join de rayon et
• la fonction scope de rayon.

Dans ce TD, vous allez construire un serveur de messagerie (pensez à IRC par exemple) en utilisant les futures et les streams. On commencera par coder un serveur qui renvoie tous les messages à son émetteur, puis un serveur qui diffuse tous les messages à tous les clients.

Contrairement aux TDs précédents, le but ici n'est pas de paralléliser le code en utilisant plusieurs cœurs du processeur mais d'exécuteur plusieurs tâches lentes à cause de l'interaction avec les entrées/sorties sur le même cœur.

Pour construire le serveur, nous nous appuierons sur l'ensemble de bibliothèques tokio qui permet d'exposer l'interface réseau sous forme de futures et de streams. En particulier, nous utiliserons les bibliothèques tokio-core pour accéder aux fonctionnalités de base, tokio-io pour accéder aux flux de bytes transitant sur le réseau et tokio-codec pour décoder les messages envoyés par le client. Le décodage des messages entrants se fera également à l'aide de la librairie bytes qui permet de représenter des buffers de bytes.

Enfin, les futures et les streams fournis par Tokio se basent sur les traits définis dans la bibliothèque futures. En particulier, nous vous conseillons vivement de regarder la documentation des traits Future, Stream et Sink pour voir comment vous pourrez manipuler les futures et les streams.

Vous devrez ajouter les dépendances ci-dessous au fichier Cargo.toml.

[dependencies]
bytes = "0.4"
tokio-core = "0.1"
tokio-io = "0.1"
tokio-codec = "0.1"
futures = "0.1"

Par ailleurs, le TD vous demande d'écrire deux programmes différents : un client et un serveur. Vous pouvez le faire en créant deux fichiers src/bin/client.rs et src/bin/server.rs qui seront lancés avec cargo run --bin client et cargo run --bin server. Si vous souhaitez partager du code entre les deux programmes, vous pouvez le placer dans src/lib.rs puis importer le module avec extern crate <votre_crate>; (<votre_crate> est le nom indiqué dans le Cargo.toml dans la section package, par exemple extern crate td2;).

Afin de vous aider à construire le serveur, on vous donne le type ci-dessous pour représenter les erreurs. Ce type peut être construit automatiquement à partir des objets des types std::io::Error et mpsc::SendError. Pour transformer une future ou un stream ayant un de ces deux types d'erreurs en une future ou un stream sur notre type d'erreur, il suffit d'appeler la méthode .from_err::<Error>(). De la même manière, on peut appeler sink_from_err::<Error>() sur un sink. On peux aussi afficher l'erreur en la passant en argument des macros de formatage des chaines de caractères (par exemple println).

# #![allow(unused_variables)]
#fn main() {
extern crate bytes;
extern crate futures;
extern crate tokio_codec;
extern crate tokio_core;
extern crate tokio_io;

use futures::unsync::mpsc;

enum Error {
    /// Error produced by an IO opperation.
    IoError(std::io::Error),
    /// Error produced by an MPSC channel.
    SendError,
    /// The client sent an invalid frame.
    InvalidFrame,
}

impl From<std::io::Error> for Error {
    fn from(e: std::io::Error) -> Error {
        Error::IoError(e)
    }
}

impl<T> From<mpsc::SendError<T>> for Error {
    fn from(_: mpsc::SendError<T>) -> Error {
        Error::SendError
    }
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match *self {
            Error::IoError(ref e) => e.fmt(f),
            Error::SendError => write!(f, "mpsc send failed"),
            Error::InvalidFrame => write!(f, "invalid frame"),
        }
    }
}
#}

On donne aussi le type Codec pour décrire comment interpréter les bytes arrivant sur l'interface réseau et comment renvoyer les messages dans l'autre sens. La méthode decode découpe le flux d'entrée à chaque retour à la ligne et renvoie une String par ligne. La méthode encode écrit les String qu'on lui donne en entrée séparées par des retours à la ligne.

On remarquera que encode prend en réalité un compteur de référence vers une String. Cela évite de copier la chaine de caractères si elle est envoyée vers plusieurs clients. Pour plus d'informations, allez voir la documentation de Rc.

# #![allow(unused_variables)]
#fn main() {
use bytes::BytesMut;
use std::rc::Rc;
use tokio_codec::{Decoder, Encoder};

struct Codec;

impl Decoder for Codec {
    type Item = String;
    type Error = Error;

    fn decode(&mut self, buf: &mut BytesMut) -> Result<Option<Self::Item>, Error> {
        if let Some(i) = buf.iter().position(|&b| b == b'\n') {
            // Remove the serialized frame from the buffer.
            let line = buf.split_to(i);
            // Also remove the '\n'
            buf.split_to(1);
            // Turn this data into a UTF string and return it in a Frame.
            match std::str::from_utf8(&line) {
                Ok(s) => Ok(Some(s.to_string())),
                Err(_) => Err(Error::InvalidFrame),
            }
        } else {
            Ok(None)
        }
    }
}

impl Encoder for Codec {
    type Item = Rc<String>;
    type Error = Error;

    fn encode(&mut self, msg: Rc<String>, buf: &mut BytesMut) -> Result<(), Error> {
        buf.extend(msg.as_bytes());
        buf.extend(b"\n");
        Ok(())
    }
}
#}

On vous donne maintenant le code d'un client pour communiquer avec le serveur. Vous pourrez utiliser ce client pour tester votre serveur. Le client utilise les mêmes types Error et Codec que le serveur.

use futures::{stream, Future, Sink, Stream};
use tokio_core::net::TcpStream;
use tokio_core::reactor::Core;

fn main() {
    let mut core = Core::new().unwrap();
    let handle = core.handle();
    let addr = "127.0.0.1:12345".parse().unwrap();
    // Establish a conection to the server. `TcpStream::connect` produces a future that we
    // must resolve with the event loop.
    let socket = core.run(TcpStream::connect(&addr, &handle)).unwrap();
    // Obtain a sink and a stream to interface with the socket.
    let (writer, reader) = Codec.framed(socket).split();
    // Create a future that prints each message to the console.
    let printer = reader.for_each(|msg| {
        println!("{}", msg);
        Ok(())
    });
    // Add the future to the event loop, panic if an error is encountered.
    handle.spawn(printer.map_err(|err| panic!("{}", err)));
    // Create a future than send 10^9 messages.
    let sender = stream::iter_ok::<_, ()>(0..1_000_000_000)
        // Convert numbers to messages
        .map(|i| Rc::new(format!("msg {}", i)))
        // Send all messages to the sink.
        .forward(writer.sink_map_err(|err| panic!("{}", err)));
    // Spin-up the event loop until `sender` is completed.
    core.run(sender).unwrap();
}

Question 1. Lisez attentivement et comprenez le code ci-dessus. En particulier vous vous poserez les questions suivantes:

• Quel est le type de TcpStream::connect(&addr, &handle) ?
• Que fait la méthodeCore::run ?
• Quels sont les types de writer et de reader ?
• Que fait reader.for_each ? Que renvoie-t-il ? A quel moment la clôture passée en argument est-elle exécutée ?
• Que fait handle.spawn ?
• Que font les méthodes map et forward ?

On veut maintenant créer un serveur qui renvoie à chaque client les messages que celui-ci lui a envoyé. Afin de traiter les connexions entrantes, on utilisera le TcpListener. Un exemple d'utilisation est fournis ci-dessous. La méthode listener.incoming() retourne le stream des connexions entrantes.

# #![allow(unused_variables)]
#fn main() {
use tokio_core::net::TcpListener;

// Create the event loop that will drive this server
let mut core = Core::new().unwrap();
let handle = core.handle();
// Bind the server's socket
let addr = "127.0.0.1:12345".parse().unwrap();
let listener = TcpListener::bind(&addr, &handle).unwrap();

// Handle the stream of incoming connections.
let server = listener.incoming().for_each(|(socket, _)| {
    ... // TODO: handle incoming connections
});

// Spin up the server on the event loop
core.run(server).unwrap();
#}

Question 2. Créez un serveur qui renvoie chaque message reçu au client émetteur. Votre serveur devra continuer de fonctionner même si un client est tué ou si il envoie un caractère non valide (on peut tester ce dernier point en ouvrant une connexion avec telnet et en tapant Ctrl+C).

Nous allons maintenant modifier le serveur d'écho pour envoyer les messages à tous les clients. Le serveur devra répondre aux contraintes ci dessous:

• Tous les clients doivent recevoir tous les messages.
• Les messages doivent arriver dans le même ordre pour tous les clients
• Le serveur doit continuer à fonctionner même si un client se déconnecte ou envoie des données illégales.

Pour séquentialiser les messages, vous pourrez utiliser les files de messages MPSC (Multiple Producer, Single Consumer).

Question 3. Implémenter le serveur de messagerie. Modifiez le client pour mesurer le nombre de messages que peut supporter le serveur avec 1, 2 ou 4 clients.

Question 4. On souhaite compléter le serveur et/ou le client de messagerie par un pool de threads capables de gérer en parallèle des traitements calculatoires sur les messages. Par exemple, on pourra ajouter du (dé)chiffrement, de la traduction automatique, de l'analyse syntaxique et sémantique pour exploiter les données échangées par les clients, etc. Modifiez le serveur et/ou le client pour que les messages soient envoyées via une future dans un tel pool de tâches calculatoires, avant de repartir (éventuellement modifié) dans le schéma de diffusion de messages implémenté ci-dessus.

Dans ce TD, vous allez construire un petit simulateur de circuits binaires (plus précisément, un compteur) en utilisant la bibliothèque du projet. Le TD peut se faire en utilisant l'implantation séquentielle fournie ici, et vous servira de tests supplémentaire pour l'implantation parallèle de votre projet. Si vous avez déjà implanté un moteur d'exécution parallèle, vous pouvez bien sûr l'utiliser pour ce TD.

Commencez par créer dans le projet un fichier src/bin/circuit.rs contenant le code suivant (si vous avez changé le nom du projet dans le Cargo.toml, remplacez extern crate rrs en utilisant le nom que vous avez indiqué) :

extern crate rrs;

use rrs::api::prelude::*;
use rrs::common::prelude::*;

fn main() {
    // ...
}

Vous pourrez ainsi lancer votre code pour le TD à l'aide de la commande cargo run --bin circuit. Une fois que le code fonctionne, il est recommandé de l'ajouter aux tests dans src/lib.rs !

Nous allons commencer par implanter un additioneur 8 bits à l'aide du moteur d'exécution. Vous pouvez vous référer à la page wikipédia pour les détails du circuit d'un additioneur (les schémas de la version anglaise sont plus détaillés).

Question 1. En vous inspirant des tests d'exemple fournis avec le projet dans le fichier src/lib.rs, écrivez un demi-additioneur sur 1 bit en utilisant des ports booléens. Vous utiliserez pour cela le module sequential::multiple_uses, ainsi que des variables locales pour sauver le résultat de l'addition. Vérifiez que la table de vérité de votre demi-additioneur est correcte, et expliquez pourquoi il est plus simple de créer le circuit en commençant par la fin.

Question 2. La création de circuits en commençant par la fin est peu intuitif, et requiert une certaine gymnastique mentale. Nous allons donc plutôt créer les circuits en modifiant les activateurs après coup. Le code suivant définit un type utilitaire InputBuilder permettant de combiner une arête entrante avec une fonction pour y connecter un activateur, ainsi qu'une macro pour faciliter son utilisation.

# #![allow(unused_variables)]
#fn main() {
pub struct InputBuilder<E, C> {
    pub edge: E,
    pub connect: C,
}

impl<'b, 'r: 'b, E: InputEdgeMut<Runtime<'r>> + 'r, C: FnOnce(RuntimeActivator<'r>) + 'b>
    InputBuilder<E, C>
{
    pub fn new(edge: E, connect: C) -> Self {
        InputBuilder { edge, connect }
    }
}

macro_rules! Input {
    ($a:lifetime, $r:lifetime, $dtype:ty) => {
        InputBuilder<
            DataInput<RcReceiver<Cell<$dtype>>>,
            impl FnOnce(RuntimeActivator<$r>) + $a,
        >
    };
}
#}

Il peut être utilisé par exemple en définissant des méthodes additionelles sur le ScopedGraphBuilder:

# #![allow(unused_variables)]
#fn main() {
impl<'a, 'r> ScopedGraphBuilder<'a, Runtime<'r>> {
    pub fn binop<T: 'r>(
        &mut self,
        lhs: Input!['a, 'r, Option<T>],
        rhs: Input!['a, 'r, Option<T>],
        f: impl Fn(T, T) -> T + 'r,
    ) -> Input!['a, 'r, Option<T>] {
        let (out_send, out_recv) = self.port(None).split();

        let mut node = self.node(TaskNode {
            inputs: (lhs.edge, rhs.edge),
            outputs: (out_send.with_activator(Default::default()),),
            task: StrictTask::new(
                move |lhs, rhs| (Some(f(lhs.unwrap(), rhs.unwrap())),)),
        });
        (lhs.connect)(node.add_activator());
        (rhs.connect)(node.add_activator());

        InputBuilder::new(out_recv.as_data_input(), move |activator| {
            node.borrow_mut().outputs.0.activator = activator;
        })
    }
}
#}

Vous pouvez ensuite utiliser ces fonctions dans votre code:

# #![allow(unused_variables)]
#fn main() {
let (lhs_sender, lhs_receiver) = runtime.port(None).split();
let (rhs_sender, rhs_receiver) = runtime.port(None).split();

let mut lhs_in = lhs_sender.with_activator(Default::default());
let mut rhs_in = rhs_sender.with_activator(Default::default());

{
    let lhs_ref = &mut lhs_in;
    let rhs_ref = &mut rhs_in;

    runtime.build_scope(move |b| {
        let i32_add = b.binop(
            InputBuilder::new(lhs_receiver.as_data_input(), move |x| {
                *lhs_ref = x
            }),
            InputBuilder::new(rhs_receiver.as_data_input(), move |x| {
                *rhs_ref = x
            }),
            |x: i32, y: i32| -> i32 { x + y },
        );

        // Use i32_add.edge and i32_add.connect...
    })
}
#}

En suivant l'exemple du binop fourni ci-dessus, ajoutez les méthodes suivantes (qui opèrent sur des booléens) au ScopedGraphBuilder:

• not qui calcule un "non" binaire
• xor qui calcule un "ou exclusif" binaire
• and qui calcule un "et" binaire
• or qui calcule un "ou" binaire
• nand qui calcule un "non-et" binaire
• dup qui duplique son entrée

Question 3. Ajoutez au ScopedGraphBuilder une méthode half_adder construisant un demi-additioneur 1 bit, puis une méthode full_adder construisant un additioneur 1 bit. Vérifiez leurs tables de vérité, puis construisez un additioneur 4 bits en chaînant plusieurs additioneurs 1 bit (voir la section "additioneur parallèle à propagation de retenue" ou "Ripple-carry adder" sur Wikipédia). Effectuez quelques calculs simples comme 2 + 3 (0b10 + 0b11) et vérifiez que le résultat est correct.

Question 4 (optionnel). Construisez des additioneur 8, 16 et 32 bits en utilisant le principe de la retenue anticipée.

On veut maintenant gérer des circuits à travers plusieurs instants. Plusieurs mécanismes sont possibles pour gérer les instants; nous utiliserons dans le TD une liste de noeuds à exécuter à chaque instant. Au début d'un instant, les noeuds de la liste sont activés, puis on effectue une exécution classique.

Question 5. Ajoutez au runtime un nouveau champ clock de type Vec<RuntimeActivator<'r>> et modifiez la méthode execute pour qu'elle appelle tous les activateurs au début de l'instant.

Question 6. Écrivez une méthode const_fby qui calcule un retard, de signature:

# #![allow(unused_variables)]
#fn main() {
pub fn const_fby(
    &mut self,
    init: bool,
    val: Input!['a, 'r, bool],
) -> Input!['a, 'r, bool]
#}

La valeur du noeud de sortie est init au premier instant, puis la valeur de val à l'instant précédent. Vous implémenterez const_fby à l'aide de deux noeuds set et get et d'une dépendance de contrôle assurant que get est exécuté avant set au sein d'un instant. N'oubliez pas d'enregistrer get dans l'horloge!

Note : De la même façon que as_data_input et as_data_output sont fournis dans le projet, il pourra être judicieux d'ajouter une méthode as_control_output sur les activateurs pour les transformer en arêtes sans composante de données (type de donnée ()).

Question 7. En utilisant les fonctions des questions précédantes, écrivez un circuit séquentiel sur 4 (ou plus) bits qui compte en partant de 0 et s'arrête en cas d'overflow.

Question 8 (optionnel). Implémentez un circuit à une deux entrées a: bool et b: i32 et qui calcule if a { (b + 2) * 2 } else { (b * 2) + 2 } en n'utilisant une seule addition et une seule multiplication.

Le but du projet est de créer une bibliothèque de programmation réactive en Rust avec un moteur d'exécution parallèle.

La première étape du projet consiste en l'implantation d'un moteur d'exécution de tâches parallèle dans un cas simplifié, celui de l'exécution d'un graphe de flot de données. La seconde étape demande d'améliorer le moteur d'exécution avec des concepts réactifs: ajout d'une notion d'instants, de signaux, et de structures de contrôle. La troisième étape demande d'écrire une interface haut niveau permettant d'utiliser la bibliothèque. Les secondes et troisième étapes demandent d'avoir commencé la partie "programmation réactive" du cours et seront mises en ligne plus tard.

Une fois les trois étapes implémentées, vous pourrez vous atteler à étendre votre bibliothèque avec les pistes données ci-dessous. Ces pistes restent volontairement vagues: c'est à vous de définir l'approche exacte et de fournir la documentation, les tests et/ou les benchmarks pour justifier de la pertinence de votre travail. Nous vous demanderons également d'implémenter un exemple d'application (voir ci-dessous).

Afin de valider votre projet, nous vous demandons d'implémenter au moins un exemple d'application. Nous vous indiquons ci-dessous quelques possibilités mais vous êtes encouragés à proposer votre propre idée. Attention, pour espérer observer un gain de performance avec la parallélisation, faites en sorte que chaque processus ait suffisamment de travail entre chaque synchronisation.

• Implémentez un simulateur de circuit digital.
• Implémentez un jeu contenant plusieurs agents évoluant dans un monde (style pacman). Si vous voulez voir des gain de calculs avec la parallélisation, arrangez-vous pour que chaque agent ait suffisamment de travail à faire entre chaque synchronisation.
• Implémentez une simulation physique impliquant plusieurs objets.

En complément des notes de cours, vous pourrez lire les références suivantes sur le langage ReactiveML dont la sémantique inspire le projet:

• Constructions et concepts du langage ReactiveML
• Un explication de l'implémentation du langage ReactiveML

Les détails de la conception et de l'implémentation se trouvent dans la Thèse de Louis Mandel. Une implémentation parallèle est décrite dans le chapitre 9 de la thèse de Cédric Pasteur.

La lecture de ces documents ne devrait pas être nécessaire à la réalisation du projet.

Vous pouvez faire le projet soit seul, soit en binôme. Le code commenté est à rendre avant le 23 Décembre en envoyant un email à Basile Clément. Votre email doit contenir vos noms (deux pour les binômes) et une archive nommée rrs_{nom 1}_{nom 2}.tgz.

La première étape du projet consiste en l'écriture d'un moteur d'exécution parallèle pour un graphe de flot de données. Le moteur d'exécution se charge d'ordonnancer les calculs, et d'exécuter les tâches lorsque toutes leurs dépendances sont satisfaites.

Un patron contenant une API sous forme de traits et une implémentation séquentielle d'un moteur d'exécution est fourni. Le but de cette partie est d'écrire une version parallèle de l'architecture décrite ci-dessous.

Il est suggéré d'utiliser la bibliothèque crossbeam pour l'implémentation du runtime parallèle, en créant un moteur d'exécution composé de plusieurs threads. Afin de se distribuer le travail, les threads doivent soit partager leur file d'attente via des piles concurrentes, soit utiliser un mécanisme de vol de tâche.

Vous devrez également implémenter un méchanisme de synchronisation en utilisant par exemple des barrières ou des variables de condition entre les threads du moteur d'exécution. Ceci doit permettre au moteur de s'arrêter plutôt que de tourner en boucle infinie une fois que toutes les tâches sont exécutées, tout en s'assurant que les threads ne s'arrêtent pas de traiter des tâches trop tôt. Gardez à l'esprit qu'une seule tâche peut ensuite en activer un nombre arbitraire quand elle a fini de s'exécuter !

Au sein de l'API, de nombreux concepts sont définis à travers une famille de traits similaire à celle des closures, FnOnce, FnMut et Fn. Ces familles de trait permettent d'encoder les différences entre les instances du trait à utilisation unique, réutilisable avec modification d'état, et réutilisable sans modification d'état.

La communication entre les tâches est gérée par des ports (définis à travers les familles de traits Receiver et Sender). Les ports sont constituées d'une partie émettrice et une partie réceptrice: la partie réceptrice peut lire la dernière valeur qui a été écrite dans le port par la partie émettrice.

Une tâche représente un élément de calcul à effectuer. Les tâches sont définies par la famille de traits TaskOnce, Task et TaskMut dans l'API. Une tâche prend en argument un ordonnanceur, un tuple de ports d'entrée à utilisation unique et un tuple de ports de sortie à utilisation unique, et contient le code à exécuter.

Les applications bas niveau de la bibliothèque définiront généralement des tâches qui seront ensuite connectées au sein du graphe d'exécution. Afin de faciliter leur écriture, la structure StrictTask fournie dans le module common permet d'encapsuler une fonction stricte (qui utilise toutes ses entrées et définit toutes ses sorties) dans une tâche. Cette structure permet d'écrire des tâches comme des fonctions usuelles et gère automatiquement l'interaction avec les ports d'entrée et de sortie.

Vous pouvez (et devrez !) bien évidemment aussi définir des implémentations supplémentaires de la famille de traits afin d'encoder des comportements plus complexes, par exemple qui n'utilisent que certaines entrées, ne définissent que certaines sorties, ou ont un ordre précis d'utilisation de leurs ports.

Un noeud représente une tâche intégrée au graphe de flot de données. Le noeud se charge de connecter la tâche avec ses dépendances, et permet d'encapsuler le type exact des entrées et sorties de la tâche à travers un trait object de taille dynamique. Cela est nécessaire car on veut être capable de garder une list de noeuds à exécuter dans le moteur, et tous doivent donc avoir le même type. La famille de traits Node permet cette encapsulation; cependant, la seule implémentation de cette famille de traits avec laquelle il devrait être nécessaire d'intéragir est la structure TaskNode qui contient une tâche ainsi que des ports appropriés.

Le flot de contrôle au sein du graphe de tâches est encodé à travers des activateurs. Essentiellement, un activateur représente un pointeur partagé vers un noeud qui contient également un compteur, initialisé au nombre d'entrées du noeud. À chaque fois qu'une valeur est écrite dans un port d'entrée, le compteur associé à l'activateur est décrémenté et, quand il atteint zéro, le noeud est activé et sera ensuite exécuté par l'ordonnanceur.

Le moteur d'exécution implémente le trait Scheduler qui lui permet d'ordonnancer des noeuds. Il fournit également quelques méthodes supplémentaires permettant l'exécution du graphe de tâches jusqu'à ce que toutes les tâches aient été exécutées, ainsi que quelques facilités pour la création de noeuds.

Dans le patron, deux moteurs d'exécutions sont fournis: un moteur à exécution unique (single_use) qui exécute chaque tâche au plus une fois et ne permet pas la création de cycle de dépendances; et un moteur à exécutions multiples plus complexe (multiple_uses) qui peut exécuter les tâches plusieurs fois et permet l'exécution répétée de tâches sans allocation dynamique. Il est demandé d'implémenter une version parallèle de chacun de ces deux moteurs d'exécution, en commençant par la version à exécution unique, plus simple. Vous pourrez ensuite choisir entre les deux moteurs d'exécution pour les étapes suivantes du projet.

Le trait Scheduler est séparé du moteur d'exécution lui-même, et les activateurs sont en général indépendant de l'ordonnanceur exact utilisé (à partir du moment où il peut activer le bon type de noeuds): ceci permettra d'intégrer facilement des structures de contrôle telles qui possèdent leur propre liste de tâches à exécuter lorsqu'une condition est vérifiée, comme par exemple les signaux réactifs.

Lors de la création du moteur d'exécution, nous avons volontairement fourni des méthodes bas niveau de création de graphes de tâche. Cela rend la création de graphes peu aisée, et notamment (comme vu en TD) requiert d'écrire les graphes en partant de la fin. Nous allons maintenant définir une interface de création de processus réactifs en s'inspirant des bibliothèques vues en cours (futures, rayon, etc.).

Pour cette partie (et les suivantes) du projet il est demandé de choisir entre l'implémentation à utilisation unique ou utilisation multiple des noeuds. Le cas de l'utilisation multiple permet de meilleures performances, mais pose des questions additionnelles; en particulier, il faut faire attention à ne pas activer plusieurs fois un noeud au travers du même activateur avant qu'il ait été exécuté !

Les exemples et explications ci-dessous sont données en présupposant un moteur d'exécution séquentiel à utilisation unique des noeuds; c'est à vous d'adapter pour votre moteur d'exécution parallèle.

On supposera les définitions de types suivantes:

# #![allow(unused_variables)]
#fn main() {
type Activator<'r> = <Runtime<'r> as GraphSpec>::Activator;
type Builder<'a, 'r> = ScopedGraphBuilder<'a, Runtime<'r>>;

type Receiver<'r, T> = <<Runtime<'r> as PortSpec<T>>::Port as Port>::Receiver;
type Sender<'r, T> = <<Runtime<'r> as PortSpec<T>>::Port as Port>::Sender;

type ControlEdge<'r> = ControlOutput<Activator<'r>>;
type DataEdge<'r, T> = NodeInput<Activator<'r>, Sender<'r, T>>;
#}

Question 0. En vous inspirant des traits ReceiverExt et SenderExt, écrivez un trait ActivatorExt qui fournit une méthode as_control_output convertissant l'activateur en une arête.

Nous allons définir le trait ProcessOnce représentant un processus réactif pouvant être compilé en un graphe de tâches. Pour compiler un processus réactif P, on lui fournit les arêtes sur lesquelles envoyer ses sorties (qui activeront donc les noeuds appropriés), et il retourne les arêtes sur lesquelles il attend ses entrées (de type P::Inputs).

# #![allow(unused_variables)]
#fn main() {
/// A reactive process which can be compiled to a graph.
pub trait ProcessOnce<'r, Outputs: Tuple>: ProcessOnceExt + 'r {
    /// The input edges produced when compiling this process.
    type Inputs: Tuple;

    /// Compile the reactive process down to a graph.
    fn compile_once<'a>(self, b: &mut Builder<'a, 'r>, outputs: Outputs) -> Self::Inputs;
}

/// A trait containing utility functions combinators for processes.
///
/// This is a separate trait from ProcessOnce in order to simplify the
/// typechecking: when rust sees code such as `p1.join(p2)`; it only needs to check
/// that `p1` implements `ProcessOnceExt` and can delay the actual typechecking
/// of the input/output edges until a larger definition is provided.
pub trait ProcessOnceExt {
    fn map<F, I, O>(self, fun: F) -> Map<Self, F, I, O>
    where Self: Sized,
          F: FnOnce(I) -> O,
    {
        Map { process: self, fun, _funtype: PhantomData }
    }

    // TODO: Add combinators here :)
}

struct Map<P, F, I, O> {
    process: P,
    fun: F,

    /// This is used to tell Rust type inference about the `I` and `O` types to
    /// use for this function.  The same type `F` can implement `FnOnce(I) -> O`
    /// for multiple `I` and `O` types, and without this, the typechecker can
    /// easily get confused as to which input/output types we actually meant
    /// and require manual annotations.
    /// This ensures that a single, coherent type is used for a `Map` value
    /// even if the underlying `F` type is compatible with several input/output
    /// types.
    _funtype: PhantomData<fn(I) -> O>,
}
#}

Lors de l'implémentation du trait ProcessOnce on essayera autant que possible de rester général sur les types Outputs compatibles. Par exemple on définit ainsi un processus appliquant un ReceiverOnce:

# #![allow(unused_variables)]
#fn main() {
struct Recv<R> {
    receiver: R,
}

impl<R> ProcessOnceExt for Recv<R> {}

impl<'r, O: 'r, R: 'r> ProcessOnce<'r, (O, )> for Recv<R>
where
    R: ReceiverOnce,
    O: OutputEdgeOnce<Runtime<'r>, Item = R::Item>,
{
    type Inputs = (ControlEdge<'r>, );

    fn compile_once<'a>(self, b: &mut Builder<'a, 'r>, (output, ): (O, )) -> Self::Inputs {
        let activator = b.node(TaskNode {
            inputs: (),
            outputs: (output, ),
            task: StrictTask::new(move || (self.receiver.recv_once(), )),
        }).add_activator();

        (activator.as_control_output(), )
    }
}
#}

Question 1. Écrivez une fonction ready qui prend une valeur de type V et construit un processus renvoyant la valeur, et une fonction lazy qui encapsule une cloture dans un processus réactif qui retourne le résultat de son exécution.

Question 2. Implémentez le trait ProcessOnce pour les valeurs de type Map défini ci-dessus.

Question 3. Ajoutez au trait ProcessOnceExt une méthode flatten qui exécute le processus retourné par un autre processus, ainsi qu'une méthode then équivalente à map(..).flatten(). Vous pourrez vous inspirez de la déclaration de ces méthodes pour le trait Future. Il vous faudra probablement également implémenter le trait TaskOnce.

Question 4 (optionnel). Dans la question précédente, les fonctions flatten et then que nous avons définies demandent de compiler un nouveau processus pendant son exécution, ce qui peut être couteux. En réutilisant le processus Recv donné en example plus haut, ajoutez une méthode static_then au trait ProcessOnceExt. Un exemple d'utilisation est donné ci-dessous.

# #![allow(unused_variables)]
#fn main() {
ready(3).static_then(|(recv_three, )| {
    println!("Currently compiling...");
    recv_three.map(|(three, )| println!("{} = 3", three))
})
#}

Question 5. Lorsque l'on compile un processus, on veut pouvoir récupérer sa valeur. Implémentez le trait OutputEdgeOnce pour la structure ProcessOutput ci-dessous, puis écrivez une fonction execute_process qui prend un processus en argument, l'exécute dans un nouveau moteur d'exécution, et écrit sa valeur dans une variable donnée en argument (on a besoin de prendre la variable de sortie en argument car autrement la durée de vie 'r du moteur d'exécution devrait être inférieure à celle de la fonction execute_process, ce que l'on ne peut pas exprimer en Rust).

# #![allow(unused_variables)]
#fn main() {
struct ProcessOutput<'a, T: 'a> {
    target: &'a mut T,
}

fn execute_process<'r, I: 'r, T: 'r, P>(process: P, input: I, out: &'r mut T)
where
    P: ProcessOnce<'r, (ProcessOutput<'r, T>, )>,
    P::Inputs: OutputEdgeOnce<Runtime<'r>, Item = I>,
{
    // TODO
}
#}

On veut maintenant implémenter la composition parallèle || sous la forme d'une méthode join, telle que p1.join(p2) créé un nouveau processus retournant le couple des valeurs produites par p1 et p2.

Question 6. Implémentez la méthode join, puis exécutez avec votre moteur un processus qui affiche "a" et "b" en parallèle.

On souhaite maintenant introduire une notion d'instants dans le moteur d'exécution. Pour cela, on va utiliser la même technique que dans l'implémentation de ReactiveML: une liste de noeuds à activer à l'instant suivant.

Question 7. Ajoutez au moteur d'exécution une méthode pause qui prend en argument un Handle et l'enregistre dans une liste next qui sera exécutée à l'instant suivant, puis adaptez la méthode execute en conséquence.

Question 8. Ajoutez une méthode pause au trait ProcessOnceExt, puis écrivez le processus ReactiveML suivant en Rust et exécutez-le:

(print_endline "instant 0") ||
(pause; print_endline "instant 1") ||
(pause; pause; print_endline "instant 2")

On veut pouvoir implémenter la construction while de ReactiveML. Pour ce faire, on définit le type LoopStatus:

# #![allow(unused_variables)]
#fn main() {
pub enum LoopStatus<V> { Continue, Done(V) }
#}

Question 9. Implémentez une fonction while_ qui prend en argument une fonction retournant un processus de valeur de retour LoopStatus et retourne un processus effectuant la boucle. On notera qu'il est impossible de faire une version statique de cette fonction à moins d'utiliser le moteur à exécutions multiples; il faut donc recompiler un processus à chaque itération.

Le moteur d'exécution et les processus sont en place et nous allons maintenant nous attaquer à l'implémentation des signaux. Pour cela, on commencera par le cas des signaux "purs" sans valeur associée, qui seront ensuite améliorés pour créer des signaux avec valeurs.

On utilisera pour l'implémentation une structure de donnée partagée entre toutes les références d'un signal et qui gérera l'attente et l'émission du signal. On définit donc les types SignalRuntime ainsi que SignalRuntimeRef qui encapsule les références au SignalRuntime:

# #![allow(unused_variables)]
#fn main() {
pub struct SignalRuntime<'r> {
    // TODO: define the fields
}

pub struct SignalRuntimeRef<'r> {
    signal_runtime: Rc<SignalRuntime<'r>>,
}

impl<'r> SignalRuntimeRef<'r> {
    /// Sets the signal as emitted for the current instant.
    fn emit(&self, runtime: &mut Runtime<'r>) {
        unimplemented!()
    }

    /// Resets the signal value, clearing the emitted flag.  This is called at
    /// end of instant.
    fn reset(&self, runtime: &mut Runtime<'r>) {
        unimplemented!()
    }

    /// Register a pair of activators for the `present` construct.  The
    /// `present` activator should be called when the signal is emitted, and
    /// `not_present` should be called during the next `reset` if the signal
    /// was not emitted.
    fn register_present(
        &self,
        runtime: &mut Runtime<'r>,
        present: Activator<'r>, 
        not_present: Activator<'r>,
    ) {
        unimplemented!()
    }

    // TODO: Add other methods here
}
#}

Le SignalRuntimeRef expose des méthodes permettant d'interagir avec le signal. On vous donne la signature de deux méthodes pour émettre et réinitialiser le signal, ainsi que pour enregistrer des activateurs correspondant à la construction present de ReactiveML; à vous de rajouter des méthodes supplémentaires selon vos besoins.

Le SignalRuntimeRef ne sera pas directement exposé à l'utilisateur de la bibliothèque car on ne veut pas avoir besoin de manipuler directement des activateurs. On définit donc un trait Signal qui fournit des méthodes retournant des processus qui correspondant aux différentes constructions de ReactiveML.

# #![allow(unused_variables)]
#fn main() {
pub trait Signal<'r> {
    fn runtime(self) -> SignalRuntimeRef<'r>;
}

pub trait SignalExt {
    fn emit(self) -> Emit<Self> where Self: Sized {
        Emit { signal: self }
    }

    fn present(self) -> Present<Self> where Self: Sized {
        Present { signal: self }
    }

    // TODO: Add other methods here
}

impl<Sig> SignalExt for Sig where Sig: Signal {}

struct<Sig> Emit<Sig> {
    signal: Sig,
}

impl<Sig> ProcessOnceExt for Emit<Sig> {}

impl<'r, O: 'r, Sig: 'r> ProcessOnce<'r, O> for Emit<Sig>
where
    O: Tuple + OutputEdgeOnce<Runtime<'r>>,
    O::Item: Default,
    Sig: Signal<'r>,
{
    type Inputs = (ControlEdge<'r>, );

    fn compile_once<'a>(self, b: &mut Builder<'a, 'r>, outputs: O) -> Self::Inputs
    {
        unimplemented!()
    }
}

struct<Sig> Present<Sig> {
    signal: Sig,
}

impl<Sig> ProcessOnceExt for Present<Sig> {}

impl<'r, Sig: 'r> ProcessOnce<'r, (ControlEdge<'r>, ControlEdge<'r>)> for Present<Sig>
where
    Sig: Signal<'r>,
{
    type Inputs = (ControlEdge<'r>, );

    fn compile_once<'a>(
        self,
        b: &mut Builder<'a, 'r>,
        (present, not_present): (ControlEdge<'r>, ControlEdge<'r>),
    ) -> Self::Inputs
    {
        unimplemented!()
    }
}
#}

Question 1. Créez un object PureSignal qui implémente le trait Signal. Ce signal doit pouvoir être émit, attendu (avec la construction await immediate), et on doit pouvoir tester sa présence (avec la construction present).

Question 2. Testez votre implémentation sur le programme ci-dessous:

signal s in
loop
  emit s;
  pause;
end
||
loop
  present s then begin
    print_endline "present";
    pause;
  end else print_endline "not present";
end
||
loop
  await immediate s;
  print_endline "s received";
  pause;
end

En ReactiveML la valeur d'un signal peut être lue par plusieurs processus car il s'agit en réalité d'un pointeur vers un objet géré par le ramasse-miettes. En Rust, il n'y a pas de ramasse-miettes et il faut donc soit copier la valeur, soit s'assurer que l'on ne peut pas récupérer la valeur d'un signal plusieurs fois. On distinguera donc deux types de signaux: les signaux à consommateurs multiples (qui copient), et les signaux à consomatteur unique.

Question 3. Créez un signal à consommateurs multiples. Ce signal devra supporter aumoins les constructions emit, await, await immediate et present de ReactiveML. Vous pourrez implémenter un ReceiverOnce pour le signal et réutiliser la construction Recv définie plus haut pour le transformer en un processus.

Question 4 (optionnel). Créez un signal à consommateur unique. Pour vous assurer de l'unicité du consommateur, vous pouvez vous appuyer sur le système de types de Rust, par exemple en utilisant une approche similaire à celle des files de messages de la bibliothèque standard.

On souhaite maintenant ajouter la possibilité d'attendre sur plusieurs événements à la fois, ou sur l'un ou l'autre de deux événements. Ceci correspond aux configurations événementielles de ReactiveML.

Cette partie est optionnelle et n'est fournie que pour donner des pistes sur l'implémentation des configurations événementielles. Il est plus important que vous ayez bien compris les parties précédentes que de s'attaquer à cette partie.

Question 5. En vous inspirant du SignalRuntime, créez une structure AndRuntime qui pointe vers deux SignalRuntime et fournit les méthodes emit, cancel et reset. emit sera appelé par chacun des SignalRuntime quand ils sont émis (il faut donc deux appels à emit avant d'activer les tâches en attente), tandis que cancel sera appelé en fin d'instant par les SignalRuntime si ils avaient été émis durant l'instant. Enfin reset sera appelé en fin d'instant, comme pour le SignalRuntime. Il peut être judicieux de créer un trait Resettable pour stocker les signaux et configurations ensemble dans le moteur d'exécution.

Question 6. En vous inspirant de la question précédente, créez une structure OrRuntime fournissant les même méthodes que AndRuntime, mais qui active les processus en attente dès réception de l'un ou l'autre des signaux. OrRuntime doit permettre d'enregistrer deux processus différents à exécuter selon le signal qui a été émis (attention: un seul de ces processus doit être exécuté, même quand les deux signaux sont émis ! Pour respecter les hypothèses de synchronicité, le processus exécuté ne doit pas dépendre de l'ordre d'émission des signaux).

Question 7. Implémentez des configurations événementielles valuées en vous basant sur AndRuntime et OrRuntime.

On peut maintenant implémenter les constructions avancées du langage ReactiveML comme le do .. when s ou le do .. until s en se basant sur ces configurations événementielles. On pourra considérer l'existence d'un signal spécial tick, toujours présent et automatiquement émis par le moteur d'exécution en début d'instant (ainsi la construction pause par exemple est équivalente à await tick).

On peut alors transformer les do .. when s an ajoutant le signal s à toutes les instructions await (et en transformant donc pause en await tick /\ s) et en introduisant un await immediate s en début du corps. Similairement, le do .. until s -> e2 s'implémente en ajoutant une disjonction: par exemple, à l'intérieur du corps, pause; e1 devient await (s -> e2) \/ (tick -> e1) en supposant que la première branche du await est préférée.

Question 8. En vous basant sur le trait ProcessOnce, créez des traits ProcessOnceWhen et ProcessOnceUntil permettant la compilation de leur corps à l'intérieur d'un do .. when et d'un do .. until respectivement.

• Transparents du cours

• Cours CIS 198 à U. Penn

• Ainsi que des présentations additionnelles sur la page dédiée aux supports de cours.

Pour installer Rust, il faut se rendre sur le site du langage et suivre les instructions. Dans le cas où préféreriez utiliser votre gestionnaire de paquets, assurez-vous que cargo, le gestionnaire de dépendances de Rust, soit aussi installé.

Le Rust Book est la source d'information la plus complète concernant Rust. En plus d'une description détaillée des fonctionnalités du langage, il propose un tutoriel très basique pour prendre en main Rust et les outils associés. Plus concis, Rust by Example explique les constructions du langage et les fonctions de la bibliothèque standard sous forme d'exemples. Il est conseillé de commencer avec le Rust Book, puis de piocher entre le deux sites selon vos préférences.

Rust est fourni avec une bibliothèque standard dont la documentation est disponible ici. Celle-ci fournit de nombre types, objets et fonctions de base, comme les tableaux, les tables de hachage, les opérations d'entrée/sortie ou la manipulation des chaînes de caractères pour n'en citer que quelques uns.

Plutôt que d'utiliser le compilateur Rust - rustc - pour compiler votre code, il est préférable d'utiliser cargo. Cet outil se charge de télécharger les dépendances, de compiler les fichiers dans le bon ordre et de gérer les différentes options de compilation. La documentation de cargo est disponible ici.

Les commandes a connaître sont:

• cargo init --bin pour initialiser un projet Rust géré par Cargo.
• cargo build et cargo build --release pour compiler le projet, en mode debug (sans optimisations dans le code généré) ou release (avec optimisations, mais plus lent à compiler). L'exécutable généré se trouve dans target/debug/ ou target/release/.
• cargo run et cargo run --release pour compiler et exécuter le code.

Les bibliothèques produites par la communauté Rust sont publiées sur le site crates.io. Ce site fourni des options de recherche pour trouver les bibliothèques répondant à vos besoins. Une fois une bibliothèque trouvée, vous pouvez l'ajouter comme dépendance de votre projet en modifiant le fichier Cargo.toml à la racine de votre projet. Par exemple, pour utiliser la version 0.8 de la bibliothèque rayon, il faut ajouter la ligne:

rayon = "0.8"

dans la section [dependencies] de votre fichier Cargo.toml.

Vous pouvez accéder à la documentation de chaque bibliothèque sur le site docs.rs.

L'API de benchmark de Rust est un work-in-progress et demande donc l'utilisation d'une version instable (nightly) du compilateur. Vous pouvez l'installer avec: rustup install nightly, et activer la version nightly du compilateur avec rustup default nightly. Attention, c'est un changement de configuration global. Alternativement vous pouvez remplacer vos appels à cargo par rustup run nightly cargo

Note: Il existe une librairies rustc-test qui permet d'utiliser cette API avec les versions stables de Rust; malheureusement, elle ne fonctionne plus depuis rust 1.24.

On peux ensuite écrire un benchmark en créant une fonction précédée de l'attribut [bench] qui prend en argument une référence mutable vers un Bencher, comme dans l'exemple ci-dessous. Le code à évaluer doit être donné en argument à la méthode Bencher::iter. Cette méthode exécute plusieurs fois la clôture donnée en argument et affiche le temps d'exécution moyen dans la console.

Attention: il faut indiquer #![feature(test)] et extern crate test dans le fichier main.rs du projet. Le #![feature(test)] indique à Rust d'activer les APIs expérimentales du module de test, dont l'API de benchmark.

# #![allow(unused_variables)]
#![feature(test)]

#fn main() {
extern crate test;

use test::Bencher;

/// Adds two vectors
fn add_vec(lhs: &Vec<u32>, rhs: &Vec<u32>) -> Vec<u32> {
  lhs.iter().zip(rhs).map(|(lhs, rhs)| lhs+rhs).collect()
}

/// A benchmark for the `add_vec` function.
#[bench]
fn bench_add_vec(bencher: &mut Bencher) {
    // Initialize the benchmark data.
    let input_lhs = vec![1, 2, 3, 4, 5];
    let input_rhs = vec![5, 4, 3, 2, 1];
    // Let the bencher compute the average execution time.
    bencher.iter(|| add_vec(&input_lhs, &input_rhs));
}
#}

Pour compiler et exécuter tous les benchmarks, il suffit de lancer la commande cargo bench (ou rustup run nightly cargo bench).

Il est parfois utile de partager des données lourdes à initialiser entre plusieurs benchmark. Pour cela, il faut déclarer une variable statique (équivalent de globale en C). Le problème est que des variables statiques ne peuvent être initialisées qu'avec des constantes. Pour contourner ce problème, on peut utiliser la bibliothèque lazy static qui fournis une macro pour déclarer des variables statiques qui s'initialisent lors du premier accès.

Pour cela, il faut ajouter lazy_static = "1.1" comme dépendence au fichier Cargo.toml puis déclarer les variables comme suit.

# #![allow(unused_variables)]
#fn main() {
#[macro_use] extern crate lazy_static;

lazy_static! {
    static ref COSTLY_DATA: Vec<usize> = {
        // Initialisation de COSTLY_DATA
        (0..1000).map(|i| i*i).collect()
    };
}

/// Exemple d'utilisation
#[bench]
fn use_data(bencher: &mut Bencher) {
    bencher.iter(|| COSTLY_DATA.iter().sum::<usize>());
}
#}