À la question de la division

Nous avons eu l'occasion de mener un petit exercice tactique extrêmement intéressant

Dans le processus de recherche d'un nouveau MK d'une entreprise bien connue basée sur l'architecture Cortex-M4 (j'écrirai certainement à ce sujet plus tard), la question s'est posée de la rapidité avec laquelle l'opération de division entière dans l'implémentation matérielle peut fonctionner. L'expérience à grande échelle a donné un résultat quelque peu inattendu: la division d'un nombre 32 bits en un nombre 32 bits est effectuée sur 3 cycles d'horloge de la fréquence du processeur - enfin, peu importe la vitesse. Il s'est avéré que cela n'a lieu qu'avec certains opérandes, mais d'autres études ont montré que jamais le temps de terminer la division ne dépasse pas 7 mesures. Les résultats obtenus ont provoqué une légère précipitation ("et ce n'est pas une certaine forme de discours, qui ne sait pas ce que cela signifie, mais un verbe très spécifique" - Divov, comme toujours, est incomparable).

Eh bien, vous ne pouvez pas simplement prendre et diviser rapidement des nombres aussi longs, c'est étrange comme ça, mais les faits sont obstinés. J'ai imaginé la photo que le président de la Fédération de Russie m'appelle demain et me confie la tâche de ne pas rendre MK pire que celle d'ARM (je conviens que la photo est délirante, mais elle ne se produit pas dans le monde), mais je le regarde confus et je comprends que Je ne serai pas en mesure de faire une telle division de tels nombres dans un tel laps de temps, et je ne serai pas à la hauteur des attentes qui m'ont été imposées (enfin, en fait, je peux toujours acheter une licence d'ARM tranquillement et prétendre que j'ai tout inventé moi-même, beaucoup le font, mais Le PIB attend quelque chose de complètement différent de moi, et puis - je peux le tromper, mais il est peu probable que je le fasse).

Et j'étais triste que les gars d'ARM soient beaucoup plus intelligents que moi, et j'ai regardé avec envie sur Internet pour voir comment ils le faisaient. Je n'ai trouvé aucune information sur le temps d'exécution sur le site Web d'ARM, dans l'un des documents sur STM32, il a été indiqué que la division prend de 2 à 7 cycles d'horloge, ce qui correspond aux observations, mais il n'y a aucune information sur la façon dont cela est fait.

En général, l'Internet omnipotent n'a pas beaucoup aidé, il y a des astuces avec division par constante, j'ai écrit à leur sujet dans l'un des articles, mais nous avons une situation différente, il y a l'algorithme de Newton et sa version accélérée, mais ce n'est clairement pas le cas, il existe un algorithme basé sur Transformée de Fourier, mais pour un très grand nombre et il est peu probable qu'elle soit achevée en 7 cycles, même sur l'architecture ARM. J'ai dû le trouver moi-même et une solution a été trouvée, et si simple et évidente que cela devient quelque peu gênant du fait que cela n'a pas été fait immédiatement après la formulation de la tâche.

Avant de prendre ma décision, je vous suggère de trouver la vôtre, puis de comparer avec la mienne, et si elles diffèrent, je vous attends dans les commentaires.

Alors, comment divisons-nous rapidement (en pas plus de 7 cycles) deux nombres 32 bits pour obtenir un résultat 32 bits.

Pour commencer, nous rappelons comment la division en arithmétique binaire est généralement effectuée dans
forme classique. L'algorithme est assez simple et direct - nous soustrayons le diviseur du dividende. Si le résultat n'est pas négatif (nous divisons les nombres non signés), faites alors le chiffre suivant du résultat égal à un et considérez le résultat comme le prochain dividende, sinon le bit suivant du résultat est 0. Avant la mesure suivante, nous divisons par deux le diviseur (soit le déplacer vers la droite, ou déplacer le dividende vers la gauche) et réduire le poids du bit de 2 fois (par des décalages similaires). Ainsi, nous obtenons un bit du résultat en un cycle d'horloge et l'ensemble de l'opération durera 32 cycles d'horloge. Il y a encore un changement initial dans ce processus, mais cela n'affecte pas l'évaluation de la situation dans son ensemble. Nous allons accélérer, mais comment?

Nous notons que l'algorithme résultant ressemble fortement au fonctionnement d'un ADC avec une approximation séquentielle et rappelons qu'il existe d'autres méthodes de conversion, beaucoup plus rapides - la conversion parallèle. Et si ...

Nous allons soustraire du diviseur non seulement le dividende, mais le dividende * 2 et le dividende * 3 (en même temps, sur trois additionneurs), puis nous obtiendrons trois bits (signes de résultats) des informations, qui prennent 4 valeurs différentes, de sorte que vous pouvez en extraire 2 bits à la fois résultat. Ensuite, nous extrapolons une approche similaire pour 3,4,5 bits du résultat.
Pour obtenir 5 bits d'informations par cycle, nous avons besoin de 31 additionneurs, sur chacun desquels l'opération Dividend-Divisor * n (1-31) sera effectuée, les signes du résultat passent par l'encodeur et nous recevrons immédiatement 5 bits du résultat. Ensuite, nous décalons le dividende de 5 chiffres vers la gauche et répétons jusqu'à ce que vous soyez prêt. Ensuite, nous avons besoin de 32/5 = 6,4 => 7 mesures pour terminer l'opération.

Pour le travail, nous avons besoin de 31 + x additionneurs, cela semble être beaucoup, mais nous les avons déjà, car nous avons une opération de multiplication 32 * 32 par cycle, et pour l'implémenter, nous ne pouvons pas nous passer de 32 additionneurs (enfin, je pense que oui ... ), pour que nous ayons déjà l'équipement nécessaire, la seule question est de construire un circuit de contrôle et un tas de multiplexeurs pour réaliser un décalage rapide, mais cela est complètement résoluble.

Ainsi, la tâche de diviser en 7 étapes est résolue, la question demeure - comment ce temps peut-il être réduit, car dans le MK étudié, il est inférieur à 7. La solution évidente consiste à déterminer le nombre du chiffre le plus significatif du dividende (H) et du diviseur (3) au stade de la préparation de l'algorithme il deviendra immédiatement clair combien de bits hauts du quotient sont égaux à zéro, de sorte que nous pouvons sauter la première ou plusieurs phases de l'algorithme. Par exemple, si C <3, alors le résultat est immédiatement nul et nous terminons l'opération, c'est sûr que vous pouvez dériver une formule pour le nombre de mesures, mais je m'ennuyais déjà.

Fait intéressant, l'opération udiv ne donne que le quotient, bien que le reste reste évidemment quelque part à l'intérieur. En principe, il n'est pas difficile de l'obtenir en deux étapes, ce qui a été fait dans le fragment étudié du code machine en exécutant le pseudo-code Divisible-Private * Divider, mais c'est pour 2 étapes, pourquoi ne pas le diffuser immédiatement dans la paire de registres - je ne connais pas la réponse à cela une question.

En général, respectez le PIB, dites-lui que nous ferons définitivement la division en MK si ça l'intéresse encore.

PS: Au fait, lorsque je cherchais du KDPV (comme vous l’avez remarqué, je ne l’ai pas trouvé), j’en ai remarqué un avec l’inscription franchement incorrecte "Vous ne devez pas diviser par zéro." Je dois dire avec certitude qu'il est possible de diviser par zéro, ne peut pas être divisé. Mais sérieusement, dans différentes architectures, ils se divisent par zéro différemment, en x86, nous obtenons une exception (c'est une erreur inoubliable 200), dans certains, nous obtenons un dividende ou zéro, mais je n'ai jamais vu l'entier maximum. Dans ARM n / 0 = 0/0 et il s'avère 0.