Recherche de maximum
1. Spécification du module de recherche de maximum
Etant donnés
2n nombres,
le problème est de trouver leur maximum.
Les contraintes sont habituelles :
à la fois le temps de calcul et la surface d'implémentation doivent être minimisées.
2. Architecture "à gros grain"
Dans cette architecture, l'arbre est généré à partir des capacités de
datapath du synthétiseur logique
pks_shell.
Les sources sont disponibles dans le répertoire
src suivant.
3. Architecture "à petit grain"
Cette architecture est optimisée par
bit-slice "
manuellement".
On définit l'algorithme de comparaison "MSB en tête" suivant :
- Si a15 > b15 (ou vice-versa),
alors on peut d'emblée savoir que le résultat sera a (ou b)
pour tous les bits i < 16.
- Sinon, on procède à la comparaison des bits de poids juste inférieur (a14 et b14).
Une implantation possible de cet algorithme consiste à adjoindre deux signaux,
DetA et
DetB à
a et
b.
Ces signaux portent la signification suivante :
- Si DetA = 1, alors, c'est acquis, a est plus grand que b.
Ce signal est en fait vectoriel, car la décision de supériorité de a peut être reportée dans les bits d'indice i faibles,
lorsque a et b diffèrent peu.
- Si DetA = 0, alors b est plus grand que a (découverte faite à partir d'un certain indice i) si DetB = 1.
Autrement, DetA = DetB = 0 ne permet pas encore de trancher.
- En tout état de cause, il est impossible d'avoir DetA = DetB = 1
si par construction DetA15 = DetB15 = 0.
La table de vérité du résultat
si et des propagateurs de supériorité
Det{A,B}i est donnée dans la figure suivante.
| DetAi |
DetBi |
ai |
bi |
DetAi-1 |
DetBi-1 |
si |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
| 0 |
0 |
1 |
0 |
0 |
1 |
1 |
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
| 1 |
0 |
X |
X |
1 |
0 |
A |
| 0 |
1 |
X |
X |
0 |
1 |
B |
|
En déduire l'écriture en VHDL du module de comparaison MSB en tête.
Quelle architecture est-t-elle la meilleure ?
La présentation des résultats est disponible dans :
max.ppt ou
max.pdf.
