Wir hatten die Möglichkeit, eine kleine, aber äußerst interessante taktische Übung durchzuführen
Bei der Recherche nach einem neuen MK eines bekannten Unternehmens, das auf der Cortex-M4-Architektur basiert (darüber werde ich später definitiv schreiben), stellte sich die Frage, wie schnell die Ganzzahldivisionsoperation bei der Hardwareimplementierung funktionieren kann. Das vollständige Experiment ergab ein etwas unerwartetes Ergebnis: Das Teilen einer 32-Bit-Zahl durch eine 32-Bit-Zahl erfolgt über 3 Taktzyklen der Prozessorfrequenz - egal wie schnell sie ist. Es stellte sich heraus, dass dies nur bei bestimmten Operanden geschieht, aber weitere Studien haben gezeigt, dass die Zeit, die zum Abschließen einer Division benötigt wird, niemals 7 Takte überschreitet. Die erhaltenen Ergebnisse verursachten einen leichten Ansturm ("und dies ist keine bestimmte Redewendung, die nicht weiß, was sie bedeutet, sondern ein sehr spezifisches Verb" - Divov ist wie immer unvergleichlich).
Nun, man kann nicht einfach so lange Zahlen nehmen und schnell teilen, das ist seltsam, aber die Fakten sind hartnäckig. Ich stellte mir das Bild vor, dass der Präsident der Russischen Föderation mich morgen zu ihm rief und mir die Aufgabe stellte, MK nicht schlechter als das von ARM zu machen (ich stimme zu, dass das Bild eine Wahnvorstellung ist, aber es passiert nicht in der Welt), aber ich sehe ihn verwirrt an und verstehe das Ich werde in einer solchen Zeit nicht in der Lage sein, eine solche Aufteilung solcher Zahlen vorzunehmen, und ich werde die an mich gestellten Erwartungen nicht erfüllen (tatsächlich kann ich immer leise eine Lizenz von ARM kaufen und so tun, als hätte ich alles selbst erfunden, viele tun es, aber Das BIP erwartet etwas völlig anderes als ich und dann - ich kann es täuschen, aber ich werde es wahrscheinlich nicht tun).
Und ich war traurig, dass die Jungs in ARM viel schlauer sind als ich, und ich habe mich sehnsüchtig im Internet umgesehen, um zu sehen, wie sie das machen. Ich habe auf der ARM-Website keine Informationen zur Ausführungszeit gefunden. In einem der Materialien auf STM32 wurde angegeben, dass die Aufteilung 2 bis 7 Taktzyklen dauert, was den Beobachtungen entspricht, aber es gibt keine Informationen darüber, wie dies durchgeführt wird.
Im Allgemeinen hat das allmächtige Internet nicht viel geholfen, es gibt Tricks mit Division durch Konstante, ich habe darüber in einem der Beiträge geschrieben, aber wir haben eine andere Situation, es gibt Newtons Algorithmus und seine beschleunigte Version, aber dies ist eindeutig nicht der Fall, es gibt einen Algorithmus, der darauf basiert Fourier-Transformation, dies gilt jedoch für sehr große Zahlen und ist selbst bei ARM-Architektur wahrscheinlich nicht in 7 Zyklen abgeschlossen. Ich musste es mir selbst einfallen lassen und es wurde eine Lösung gefunden, die so einfach und offensichtlich war, dass es etwas peinlich wird, dass dies nicht unmittelbar nach der Formulierung der Aufgabe geschehen ist.
Bevor ich mir meine Entscheidung anschaue, schlage ich vor, dass Sie Ihre eigene finden und dann mit meiner vergleichen. Wenn sie sich unterscheiden, warte ich in den Kommentaren auf Sie.
Wie können wir also schnell (in nicht mehr als 7 Schritten) zwei 32-Bit-Zahlen teilen, um ein 32-Bit-Ergebnis zu erhalten?
Zunächst erinnern wir uns daran, wie die Division in der binären Arithmetik im Allgemeinen in durchgeführt wird
klassische Form. Der Algorithmus ist recht einfach und unkompliziert - wir subtrahieren den Divisor von der Dividende. Wenn das Ergebnis nicht negativ ist (wir teilen die vorzeichenlosen Zahlen), machen wir die nächste Ziffer des Ergebnisses gleich eins und betrachten das Ergebnis als nächste Dividende, andernfalls ist das nächste Bit des Ergebnisses 0. Vor dem nächsten Takt halbieren wir den Divisor (entweder verschieben Sie ihn nach rechts oder Verschieben Sie die Dividende nach links) und reduzieren Sie das Bitgewicht um das Zweifache (durch ähnliche Verschiebungen). Somit erhalten wir ein Bit des Ergebnisses in einem Taktzyklus und die gesamte Operation dauert 32 Taktzyklen. Es gibt noch eine anfängliche Verschiebung in diesem Prozess, die jedoch keinen Einfluss auf die Beurteilung der Situation insgesamt hat. Wir werden beschleunigen, aber wie?
Wir stellen fest, dass der resultierende Algorithmus dem Betrieb eines ADC mit einer sequentiellen Approximation stark ähnelt, und erinnern uns, dass es andere Konvertierungsmethoden gibt, die viel schneller sind - parallele Konvertierung. Was ist, wenn ...
Wir subtrahieren vom Divisor nicht nur die Dividende, sondern auch die Dividende * 2 und die Dividende * 3 (gleichzeitig bei drei Addierern), dann erhalten wir drei Bits (Zeichen der Ergebnisse) der Informationen, die 4 verschiedene Werte annehmen, sodass Sie 2 Bits gleichzeitig daraus extrahieren können Ergebnis. Als nächstes extrapolieren wir einen ähnlichen Ansatz für 3,4,5 Bit des Ergebnisses.
Um 5 Bits an Informationen pro Zyklus zu erhalten, benötigen wir 31 Addierer, auf denen jeweils die Dividend-Divisor * n-Operation (1-31) ausgeführt wird. Die Vorzeichen des Ergebnisses werden durch den Encoder geleitet und wir erhalten sofort 5 Bits des Ergebnisses. Dann verschieben wir die Dividende um 5 Stellen nach links und wiederholen sie, bis sie fertig ist. Dann benötigen wir 32/5 = 6,4 => 7 Maßnahmen, um die Operation abzuschließen.
Um zu arbeiten, brauchen wir 31 + x Addierer, es scheint viel zu sein, aber wir haben sie bereits, weil wir eine 32 * 32-Multiplikationsoperation pro Zyklus haben, und um sie zu implementieren, können wir nicht auf 32 Addierer verzichten (na ja, ich denke schon ... ), damit wir bereits über die notwendige Ausrüstung verfügen, besteht die einzige Frage darin, eine Steuerschaltung und einen Haufen Multiplexer zu bauen, um eine schnelle Verschiebung zu realisieren. Dies ist jedoch vollständig lösbar.
Damit die Aufgabe der Aufteilung in 7 Schritte gelöst ist, bleibt die Frage, wie diese Zeit reduziert werden kann, da sie im untersuchten MK weniger als 7 beträgt. Die naheliegende Lösung besteht darin, die Anzahl der höchstwertigen Ziffern der Dividende (H) und des Divisors (3) in der Phase der Erstellung des Algorithmus zu bestimmen Es wird sofort klar, wie viele hohe Bits des Quotienten gleich Null sind, so dass wir die erste oder mehrere Phasen des Algorithmus überspringen können. Wenn zum Beispiel C <3 ist, ist das Ergebnis sofort Null und wir schließen die Operation ab. Natürlich können Sie eine Formel für die Anzahl der Maßnahmen ableiten, aber ich war schon gelangweilt.
Interessanterweise gibt die udiv-Operation nur den Quotienten an, obwohl der Rest offensichtlich irgendwo drinnen bleibt. Im Prinzip ist es nicht schwierig, es in zwei Schritten zu erhalten, was in dem untersuchten Fragment des Maschinencodes durch Ausführen des Pseudocodes Divisible-Private * Divider durchgeführt wurde, aber dies ist für zwei beliebige Schritte, warum nicht gleich im Registerpaar angeben - ich kenne die Antwort darauf nicht eine Frage.
Treffen Sie im Allgemeinen das BIP und sagen Sie ihm, dass wir die Aufteilung in MK definitiv vornehmen werden, wenn es für ihn immer noch interessant ist.
PS: Übrigens, als ich nach KDPV gesucht habe (wie Sie bemerkt haben, habe ich es nicht gefunden), habe ich eines mit der ehrlich gesagt falschen Aufschrift "Sie dürfen nicht durch Null teilen" bemerkt. Ich muss mit Sicherheit sagen, dass es möglich ist, durch Null zu teilen, nicht geteilt werden kann. Aber im Ernst, in verschiedenen Architekturen teilen sie sich unterschiedlich durch Null, in x86 erhalten wir eine Ausnahme (dies ist ein unvergesslicher Fehler 200), in einigen erhalten wir eine Dividende oder Null, aber ich habe nie die maximale Ganzzahl gesehen. In ARM ist n / 0 = 0/0 und es stellt sich 0 heraus.