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.