Detecteur de LSB
Le detecteur de LSB indique l'index du bit de poids faible a 1 dans le bus d'entree, avec un drapeau d'activation actif seulement si au moins un bit est a 1. En balayant depuis le bas, il isole le un le plus bas, l'operation derriere le find-first-set et la logique d'allocation.
Dernier un sur 4 bits
Pour l'entree 0110 le bit le plus bas a 1 est a l'index 1, donc le detecteur sort 1 et active le drapeau. Avec 0000 rien n'est a 1, le drapeau reste bas et l'index est indefini.
| Input | Enable | Index |
|---|---|---|
| 0000 | 0 | - |
| 0001 | 1 | 0 |
| 0010 | 1 | 1 |
| 0100 | 1 | 2 |
| 0110 | 1 | 1 |
| 1000 | 1 | 3 |
Isoler le un le plus bas
Sur 8 bits le detecteur renvoie le premier 1 vu depuis l'extremite de poids faible. Pour 01101000 le dernier un est a l'index 3. L'astuce classique x ET (-x) isole ce meme bit sous forme de masque.
Allocateur find-first-free
Les pools de ressources gardent un bitmap ou 0 marque un emplacement libre. En l'inversant et en prenant l'index du LSB on obtient le premier emplacement disponible en une etape, le coeur des allocateurs de tampons, des listes de prets de l'ordonnanceur et des arbitres round-robin.
Citations
- Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Référence 1
- Mano, M. M., & Ciletti, M. D. (2018). Digital design: With an introduction to the Verilog HDL, VHDL, and SystemVerilog (6th ed.). Pearson.
- Wakerly, J. F. (2018). Digital design: Principles and practices (5th ed.). Pearson.