Warum werden Überläufe im binären Teilungsalgorithmus der nicht wiederherstellenden Hardware weggelassen?

Überblick

Da Sie angeben, dass Sie mit nicht wiederherstellender Division nicht vertraut sind, ziehen Sie die folgende Diskussion über Multiplikation in Betracht, um einen mentalen Kontext für das Folgende zu schaffen:

• Bei der Computermultiplikation stellt man sich den Multiplikanden und den Multiplikator in der Regel gleich breit vor (gleiche Anzahl Bits), obwohl sie nicht unbedingt gleich sein müssen. Die Breite des resultierenden Produktwerts muss die Summe aus der Breite des Multiplikanden und dem Multiplikator sein. Dadurch wird sichergestellt, dass Sie das Ausgabeergebnis nicht überlaufen lassen können.
• Sie können auch die Idee in Betracht ziehen, diesem Produkt jetzt einen kleinen Rest- Offset (der Null sein kann und daher keinen Aufwand erfordert) hinzuzufügen, um das Endergebnis zu vervollständigen.
• Dies wird als Multiply-Accumulate-Operation (oder kurz MAC) bezeichnet.
• Wenn der Multiplikand hat$N$Bits und der Multiplikator als$M$Bits, und der Summand erfordert nicht mehr als den größeren von beiden$N$oder$M$Bits, dann passt das Ergebnis der MAC-Operation hinein$N+M$Bits. (Ein Summand , der diese Größenbeschränkung erfüllt, überläuft das Produktergebnis nicht.)

(Bei der obigen MAC-Operation wird das Multiplikationsprodukt zum Augenden für die folgende Addition, wobei der kleine Offset der Summand ist .)

Um nun eine Divisionsoperation zu erstellen, die die obige MAC-Operation umkehren kann, beginnen Sie also mit einem Dividenden$N+M$bisschen breit. (Da dies die Breite des obigen MAC-Ergebnisses ist.) Sie betrachten dann auch einen Divisor$M$(oder$N$) Bits breit, um das Konzept des früheren Multiplikators (oder Multiplikanden) zu parallelisieren . Der Quotient ist dann$N$(oder$M$) Bits breit, um dem Konzept des früheren Multiplikanden (oder Multiplikators ) zu entsprechen . Der Rest wird natürlich sein$M$(oder$N$) etwas breit.

Ich denke, Sie sollten erkennen können, warum der obige Absatz eine korrekte Umkehrung der MAC-Operation ist. Wenn Sie Dinge so einrichten, dass der Dividende das ursprüngliche MAC-Ergebnis ist und der Divisor als ursprünglicher Multiplikator genommen wird , stellt der Quotient den Multiplikanden und der Rest den Summanden wieder her .

Gleiche Wortgröße (wenn N = M)

Angenommen, Sie arbeiten mit der festen Wortgröße einer ALU, sodass sowohl der Multiplikand als auch der Multiplikator jeweils gleich sind$N$Bits breit ist der Summand auch$N$Bits breit, und das Ergebnis der MAC-Operation ist dann$2\cdot N$bisschen breit.

Um eine Division durchzuführen, die die obige MAC-Operation umkehrt, ist der Dividende dann$2\cdot N$Bits breit, der Divisor ist$N$Bits breit, und der resultierende Quotient und Rest sind jeweils$N$bisschen breit.

Inzwischen sollten Sie erkennen, dass Sie mit einem Dividenden beginnen müssen , der die doppelte Wortbreite hat. Und damit der Quotient nicht überläuft , müssen Sie sicher sein, dass das obere Wort des Dividenden kleiner als der Divisor ist . (Wenn es nicht kleiner ist, ist der resultierende Quotient zu groß, um zu passen.)

Symmetrie Ihres Beispiels

Beginnen wir in Ihrem Fall mit der ursprünglichen MAC-Operation, die erforderlich ist, um Ihre Startwerte zu erhalten:

Hier ist der Multiplikand$1_8$, der Multiplikator ist$41_8$und der Zusatz ist$11_8$. Das resultierende Produkt ist$0052_8$.

Um diesen Vorgang umzukehren, setzen Sie die doppelt breite Dividende auf$0052_8$und der einfach breite Teiler zu$41_8$. (Während die Operation fortschreitet, erscheinen der resultierende Quotient und der Rest als oberer und unterer Teil des vorherigen doppelt breiten Dividendenregisters .) Da Ihre Startdividende in ein Wort passt (hier 6 Bits), ist der obere Teil einfach Null ( Natürlich.)

Der Umkehrvorgang sieht also so aus:

Alle Stücke sind noch da; nur jetzt in einem anderen Format. Ich denke, Sie sollten in der Lage sein, die Symmetrie zu sehen.

Überblick, Revisited

Hier sind ein paar erste Tests, die Sie durchführen müssen:

1. Wenn der Divisor null ist, wird mit dem Fehler "Teile durch 0" beendet.
2. Wenn die obere Hälfte des Dividenden größer als der Divisor ist , wird mit dem Fehler "Quotientenüberlauf" beendet.

Das obige Testpaar ist erforderlich, um Müll zu vermeiden, und wird vor dem Befolgen des allgemeinen Algorithmus durchgeführt.

Die Grundidee ist, dass Sie zuerst die höherwertigen Bits des Ergebnisses generieren und schließlich ganz am Ende des Prozesses das niedrigstwertige Bit generieren. Die von Ihnen durchgeführte Subtraktion (oder Addition) beginnt also mit dem hohen Wort des Doppelwort- Dividendenpaars . Deshalb findet die Subtraktion (oder Addition), die Sie sehen, auf dem statt, was schließlich der Rest wird, und nicht auf dem, was schließlich der Quotient wird . Nach dem Schalten (oder Drehen) durch$N$Bits wird der ursprüngliche Dividende so aufgeteilt, dass der Rest im oberen Wort und der Quotient im unteren Wort steht. (Der Quotient wird Bit für Bit im unteren Wort gebildet.)

Nicht wiederherstellende Abteilung; Hardware- und Softwarebeispiele

Die mathematischen Gedanken hinter der nicht wiederherstellenden Teilung sind ziemlich einfach. Annehmen$D$ist Ihr Teiler und$T_0$ist Ihre anfängliche Doppelwort- Dividende . Versuchen Sie eine Probesubtraktion für$i=1$, Wo$T_{i}=2\cdot T_{i-1} - D$(Verschiebung$T_{i-1}$links ein Bit vor dem Subtrahieren.) Wenn dies erfolgreich ist, fahren Sie mit der Berechnung fort$T_{i+1}=2\cdot T_{i} - D$, in ähnlicher Weise. Aber wenn es fehlschlägt, müssen Sie die Dinge reparieren, indem Sie etwas hinzufügen$D$bevor Sie eine weitere Schicht ausführen. In diesem Fall möchten Sie also berechnen$T_{i+1}=2\cdot \left(T_{i} + D\right)-D=2\cdot T_{i} + D$. Das ist die Essenz der nicht-wiederherstellenden Idee.

Die Implementierung ist natürlich etwas komplizierter und hängt davon ab, ob dies in Hardware oder in Software erfolgt oder nicht. Hier ist ein Beispieldiagramm, wie es in Hardware implementiert werden könnte (schließlich ist dies EESE):

(Im obigen Diagramm$Q$beginnt natürlich mit "0".)

Eine Softwareimplementierung kann eine Vielzahl von Formen annehmen (da sie eng von der Sprache und den Operatoren abhängt, die dem Programmierer zur Verfügung stehen.) Aber hier ist ein mögliches Beispiel, das dem, was Sie geschrieben haben, halbwegs nahe kommt:

Zunächst einmal zeigt das obige Diagramm, was von Programmierern als Co-Routine bezeichnet wird . Es gibt zwei unterschiedliche Schleifenaktivitäten, eine links und eine rechts, die gelegentlich ineinander übergehen. Sie können sehen, dass der Austrittsfall für die rechte Seite etwas anders ist als der Austrittsfall für die linke Seite. Dies dient dazu, eine endgültige Anpassung des Rests vorzunehmen, je nachdem, welche Schleife zu diesem Zeitpunkt aktiv war.

Wenn ich Rotationsdividende schreibe , meine ich beide Maschinenwörter; sowohl Rest als auch Quotient , die den gesamten Dividenden zu Beginn ausmachen . Aber beachten Sie, dass die Subtraktion oder Addition nur mit einem Wort stattfindet; der Rest .

Das LSB bezieht sich auf das niedrigstwertige Bit des gesamten Dividenden , was dasselbe ist wie das LSB des Quotienten . (Es liegt an Ihnen, wie Sie sich das vorstellen möchten. Es ist so oder so dasselbe.)

Das CARRY bedeutet, wie gezeigt, das Übertragsbit, das sich entweder aus der Subtraktion oder der Addition ergibt. Für den Subtraktionsfall meine ich die übliche ALU-Bedeutung, bei der eine Subtraktion tatsächlich durchgeführt wird, indem zuerst alle Bits des Subtrahends invertiert und dann plus 1 zum Minuend addiert werden . (Bei einer Subtraktion bedeutet ein Übertrag von 1, dass kein Kredit vorhanden war.)

Wenn Sie schließlich die Details der obigen Implementierungsbeispiele stören - insbesondere das$D$(der Divisor ) wird von dem subtrahiert, was das höherwertige Wort des Doppelwort- Dividenden zu sein scheint (das Wort, das schließlich zu Ihrem Rest wird ) -- dann erinnern Sie sich einfach, was ich vorher gesagt habe: Die Methode beginnt "... zuerst die höherwertigen Bits des Ergebnisses zu generieren ..." Wenn Sie genau über dieses Detail nachdenken, wird es meiner Meinung nach viel sinnvoller sein.

Notiz

Wenn ich mir Ihr Beispiel anschaue, sehe ich, dass Sie in Schritt 6 auf magische Weise ein "1"-Bit ganz rechts von Ihrem endgültigen Wert einzufügen scheinen. Das ist richtig. Aber Sie haben in Ihrer knappen Beschreibung nicht erklärt, wie es dort hingekommen ist. Die obigen Beispiele, die ich oben bereitgestellt habe, erläutern die Details darüber, wie und warum dieses Bit ankommt.