Comment le nombre entier non signé est-il implémenté dans le matériel?

10

Je travaille sur un design qui implique beaucoup de fonctions max (et des fonctions max comme arguments pour d'autres fonctions max).

Dans un effort pour simplifier la conception matérielle, je me demandais comment max est implémenté dans le matériel?

Mathématiquement, Max (a, b) peut être représenté par [(a + b) + abs (b - a)] / 2.

Est-ce ainsi que son implémentation est matérielle? (c.-à-d. par étapes; addition, division de décalage de bits, etc.)

Si oui, comment est calculé l'absolu de la différence?

James
la source

Réponses:

10

Une approche très simple serait d'implémenter (a> b)? A: b. a> b peut être implémenté en commençant à gauche et en vérifiant chaque paire de bits de (a, b):

  • 0 ou 1 à la fois: passez à la paire inférieure suivante
  • a est 1: a est le plus élevé; b est 1: b est le plus élevé

Lorsque vous savez lequel est le plus élevé, vous pouvez le sélectionner par un multiplexeur 2N-> N.

Avec une astuce astucieuse, la vérification des paires de bits peut être combinée avec le multiplexeur pour la même paire de bits.

Wouter van Ooijen
la source
2

Regardons l'algorithme dans la question:

[(a + b) + abs(b - a)]/2

Celui-ci comporte des étapes d'addition et de soustraction qui sont ensuite introduites dans une deuxième étape d'addition. La division par 2 est triviale dans le matériel, elle peut être effectuée en supprimant le LSB. Cependant, l'additionneur / soustracteur complet en deux étapes est assez lent et demande beaucoup de portes, surtout si vous cascadez plusieurs caparaçons comme vous.

S'appuyant sur la réponse de Wouter van Ooijen, la structure généralisée est un comparateur numérique alimentant le signal sélectionné d'un multiplexeur:

schématique

simuler ce circuit - Schéma créé à l'aide de CircuitLab

Le schéma ci-dessus concerne:

(A > B) ? A : B

mais notez qu'il peut être facilement reconfiguré pour toute comparaison entre les deux entrées en établissant des connexions logiques différentes entre les sorties du comparateur et le multiplexeur.

Donc, si nous savons comment formuler les trois sorties du comparateur, nous pouvons implémenter n'importe quelle comparaison dans le matériel. La logique du comparateur est bien décrite ici . Pour optimiser le matériel, nous supprimerions simplement la logique pilotant les sorties de comparateur inutilisées.

Mais au final, si ça passe au hardware, il faut passer par la synthèse. Vous ne devez donc pas vous obséder sur le schéma optimal au niveau de la porte. Au lieu de cela, optimisez votre code et vos algorithmes de manière à ne pas forcer au moins le synthétiseur à produire un résultat inefficace. "Avec une astuce astucieuse, la vérification des paires de bits peut être combinée avec le multiplexeur pour la même paire de bits", et la méthode la plus simple pour effectuer cette optimisation est la synthèse.

travisbartley
la source
1

Si vous voulez vraiment construire un circuit spécialisé pour calculer le maximum, vous pouvez commencer avec un bloc de base avec les équations suivantes:

Eje,outEje,jen¬(unejebje)Lje,out(¬Eje,jenLje,jen)(Eje,jenuneje¬bje)rje(¬Eje,jen((Lje,jenuneje)(¬Lje,jenbje)))(Eje,jen(unejebje))

puis connectez-les avec le chiffre le plus significatif alimentant le suivant. La partie critique va du MSB au LSB tandis que le circuit basé sur la soustraction aura au mieux un chemin critique allant du LSB au MSB puis revenant au LSB.

C'est l'équivalent d'un additionneur de retenue. Si vous êtes intéressé, vous pouvez créer l'équivalent des adders carry-save ou carry-select.

EL¬Eune

AProgrammer
la source