„Jeder kann das Graue Paradoxon mit Delfinen lösen, und Sie versuchen, es ohne Delfine zu tun. ""
Eigentlich wollte ich das Wochenende etwas anders verbringen, um nach Copter Huck zu gehen (nicht, dass ich ein Fan von Coptern war, nur um zu sehen, was junge Leute erfanden, um so rumzuhängen), aber die ältere Schwester war kategorisch dagegen. Natürlich bestand ich darauf (das heißt, ich kicherte ein paar Mal und sagte: "Nun, vielleicht ... es wird sowieso Spaß machen"), aber sie war unerbittlich, und als meine Frau auf ihre Seite trat, gab es keine Chance auf eine Reise. Okay, "Ich wollte es nicht wirklich", aber ich saß ein bisschen über einem lustigen Puzzle aus dem Programmierbereich, das ich mir ausgedacht hatte und über das ich berichte.
(Notwendiger Hinweis - das vergangene Wochenende war gemeint, es ist immer so - das Schreiben eines Programms dauert einige Stunden, das Schreiben eines Berichts darüber und fünf Tage Fahrt mit öffentlichen Verkehrsmitteln sind nicht abgeschlossen.)
In einem kürzlich veröffentlichten Beitrag befasste sich der Autor mit dem Problem, (unter anderem) die Berechnung von Bezier-Kurven (KB) auf MK mit relativ schwachen Parametern zu beschleunigen. Tatsächlich liegen diese Parameter auf dem Niveau des durchschnittlichen Mainframes der 70er Jahre, werden aber derzeit als eindeutig unzureichend angesehen. Aufgrund bestimmter Maßnahmen gelang es dem Autor, die Berechnungen etwas zu beschleunigen, was meiner Meinung nach eindeutig nicht ausreicht. Deshalb habe ich mich entschlossen, in erster Näherung zu schreiben, wie dies geschehen soll. Ich kenne das universelle Rezept zur Lösung von Leistungsproblemen genau - MK mit einer höheren Frequenz zu nehmen oder zu einer anderen Familie zu wechseln, aber ich komme aus der Zeit, als wir es studierten, und kostete das, was es ist, einfach weil es überhaupt nichts anderes gab. Gegenwärtig ist der Ansatz veraltet, aber es schien mir, dass er für moderne Leser von Habr nicht uninteressant wäre.
Wir geben das Problem an - wir wollen die Koordinaten der Punkte auf der Bezier-Kurve, die durch die Extrempunkte A und B und den imaginären Fokus C definiert sind, so schnell wie möglich berechnen. Die Formel zur Berechnung des Punktes P auf der Kurve ist gegeben durch
wobei T von 0 bis einschließlich 1 variiert. (Im Wiki schreiben sie, dass diese Formel einmal geheim war, es war so seltsam, aber alles ist möglich). Es ist klar, dass wir es nicht in einer komplexen Form annehmen werden, sondern separat nach den Koordinaten X und Y suchen. Wir werden die Komplexität der Berechnung unter Verwendung dieser Formel abschätzen, indem wir einfach die Anzahl der Vorzeichen arithmetischer Operationen in diesem Ausdruck zählen - 7 Multiplikationen und 5 Additionen (=> 7 * 5 +) ) Es ist möglich, dass ein guter Compiler (und jetzt sind alle Compiler gut und perfekt optimiert, wenn Sie sie nicht ausdrücklich verbieten) die Kosten auf 7 * 3 + senkt, obwohl es besser wäre, ihm zu helfen, indem Sie (1-T) im Voraus berechnen. Im Allgemeinen kann ein guter Compiler Wunder wirken, wenn alle Werte in der Formel durch Konstanten dargestellt werden. Wir gehen jedoch davon aus, dass alle Werte statisch undefiniert sind.
Erster Teil, Mathematisch
Wir beginnen den Optimierungsprozess, für den wir die Klammern öffnen und die Begriffe bei T gruppieren (vielleicht kann der Compiler dies eines Tages für uns tun, aber bisher ist dieser Teil der Arbeit der natürlichen Intelligenz zugeordnet)
=> 5 * 5 +, was deutlich besser als der Anfangswert von 7 * 5 + ist, aber relativ verbessertes 7 * 3 + sollte immer noch berücksichtigt werden.
Wenn wir uns die Zeit nehmen, um die Additionsoperation als eins abzuschließen, wird die Zeit zum Abschließen der Multiplikation in der Regel nicht weniger als eins länger sein, aber wie sehr es von der Implementierung von MK abhängt (zuerst geschrieben - über Architektur, aber dies ist nicht ganz richtig). Wenn auf dem Kristall kein Hardware-Multiplikator vorhanden ist, ist die Ausführungszeit der Multiplikation zehnmal (30+) länger als eins, und wenn sie vorhanden ist, ist sie mehrmals (1-6). Daher können wir zuversichtlich glauben, dass das Ersetzen der Multiplikation durch Addition fast immer zu einem Gewinn (und häufig zu einem signifikanten Wert) bei der Ausführungszeit führt. Nun, wir werden sofort feststellen, dass der Übergang von Festkommazahlen zu einem Gleitkomma (wir lassen den Beweis dieser Tatsache außer Acht) zu einer mehr als 20-fachen Verlängerung der Ausführungszeit für die Addition führt (die Ausrichtung ist hier sehr einflussreich), aber nur zu einer geringfügigen Zunahme für die Multiplikation . Daher unterscheiden sich für Gleitkommazahlen die Additions- und Multiplikationszeiten kaum, insbesondere relativ gesehen (wir können maximal das Zweifache erwarten), aber sie unterscheiden sich immer noch und sprechen nicht für eine Multiplikation, sodass hier ein Gewinn erzielt wird.
Zurück zum vorherigen Absatz: Wir stellen fest, dass das Rating 5 * 5 + für PT keinen signifikanten Vorteil gegenüber 7 * 3 + haben sollte, aber wir haben immer noch Reserven. Beachten Sie die Tatsache, dass wir den Satz von Punkten auf der Bezier-Kurve berechnen müssen, wenn sich der Parameter T ändert und alle anderen Parameter der Kurve fest sind (aber nicht konstant, aber schade), dann kann der Rest der Formel im Voraus berechnet werden und erhalten
=> 3 * 2 +, wobei
und
schon gut, aber wenn Sie sich an Horners Schema erinnern und schreiben
=> 2 * 2 +, dann müssen wir im Vergleich zur Entscheidung „auf der Stirn“ mehr als 2 Mal gewinnen, fast 3 Mal, und diese Optimierungen sind völlig offensichtlich.
Lassen Sie uns die Theorie mit der Praxis überprüfen (obwohl dies völlig redundant ist, sind wir von unseren Schätzungen überzeugt, aber plötzlich habe ich den Compiler unterschätzt), für die wir die Echtzeit der Ausführung verschiedener Optionen auf realer Hardware messen müssen. Nun, es ist einfach so passiert, dass ich zu Hause viele Arten von Debugging-Boards für MK von verschiedenen Unternehmen habe (einschließlich Raritäten wie Debugs von Luminary Micro oder Intel Edisson, versuchen Sie jetzt, eines zu kaufen), aber es gibt kein einziges Arduino-Board („Nun Wir haben keine Ananas “). Es scheint eine Sackgasse zu sein, aber es gibt Optionen - eine sehr interessante Website tinkercad.com hilft uns, auf der Sie Ihre Schaltung mit dem Arduino-Modul auf einem Steckbrett aufbauen, eine Skizze schreiben und sofort ausführen können. Gleichzeitig können Sie Haltepunkte setzen, das Programm Schritt für Schritt ausführen und sogar (für ein echtes Arduino beispiellos) die Werte von Variablen zum Zeitpunkt des Zusammenbruchs anzeigen.
Wir wenden uns dieser Seite zu und beginnen zu messen. Zunächst überprüfen wir unsere Annahmen über die Ausführungszeit von Operationen und erhalten nach dem Löschen der Umgebungsbedingungen die folgenden Daten für ganze Zahlen:
8 + 8 => 8 - 1 Schlag, 16 + 16 => 16 - 2,
8 * 8 => 16 - 2, 16 * 16 => 16 - 14 (das einzige, was sich als unerwartet herausstellte, ich dachte 4 * 2 + 4 * 2 = 16, es gibt interessante Optimierungen),
8/8 => 8 - 230, 16/16 => 16 - 230.
Achten Sie auf die letzten beiden Ziffern, aus ihnen geht hervor, dass die Teilungsoperation verboten ist, wenn wir wirklich schnell zählen wollen. Jetzt (endlich) messen wir die Zeit, die benötigt wird, um Operationen an der Anzahl der PTs mit der 24. Mantisse durchzuführen
a + b - 126 (und hängt stark von Operanden ab), a * b - 140, a / b - 482.
Die erhaltenen Daten korrelieren gut mit unseren theoretischen Annahmen, es ist klar, dass es an Bord dieses MK eine Hardware-Implementierung gibt: für Multiplikation, für Division, für PT-Operationen, Nr.
Nun beginnen wir, die Zeit der vollständigen Berechnung zu messen. Wir setzen die Werte A = 140, B = 120, C = 70 und bauen 170 gleichmäßig verteilte Punkte auf dem Konstruktionsbüro auf. Warum genau diese Werte - sie wurden bei der Leistungsbewertung im angegebenen Beitrag angegeben. Nachfolgend finden Sie die Algorithmen und die entsprechende Testausführungszeit.
Formel (1) => 20 ms oder 1.900 Taktzyklen pro Probe
Formel (1) => 18 ms oder 1660 Taktzyklen pro Probe (1-T separat betrachten)
Formel (2) => 16 ms oder 1540 Taktzyklen pro Probe
Formel (3) => 10 ms oder 923 Taktzyklen pro Probe
Formel (4) => 8 ms oder 762 Messungen pro Zählung
Es ist ersichtlich, dass die resultierende Verkürzung der Ausführungszeit (von 20 ms auf 8 ms) gut mit der erwarteten korreliert und wir die Berechnungen um mehr als das Zweifache beschleunigen konnten. Beachten Sie, dass wir zusätzlich zu völlig offensichtlichen Überlegungen und Mathematik, die nicht über den Schulabschluss hinausgingen, keine Notwendigkeit hatten.
Lassen Sie uns nun darüber sprechen, was zu tun ist, wenn das Ergebnis nicht ausreicht, und wir haben bereits alles aus den Berechnungsformeln herausgedrückt. Sie haben mir hier (in den Kommentaren zu einem anderen Beitrag) geschrieben, dass im Allgemeinen jedes Problem auf das Rechnen mit FT reduziert werden kann und trotz der offensichtlichen Kontroverse der Annahme (versuchen Sie dies für die numerische Lösung der Navier-Stokes-Gleichungen zu tun) in diesem speziellen Fall diese Empfehlung anwendbar ist Obwohl es wie immer Nuancen gibt.
Teil Zwei, Computing
Sobald die Änderungen am Algorithmus erschöpft sind, bleiben nur die Datenstrukturen übrig und wir betreten den Boden der Festkommazahlen. Hier finden wir viele Fallstricke, über die wir bei PT - Reichweite und Genauigkeit nicht nachgedacht haben (im Allgemeinen sollte man bei PT über diese Probleme nachdenken, aber hier ist alles einfacher, es wurde viel für uns getan). Es ist notwendig, eine kleine Untersuchung des Problems durchzuführen, um die notwendige Darstellung von FT zu bestimmen (ausgewählt in dem oben genannten Beitrag 9.7, nach den Ergebnissen zu urteilen, ist dies eindeutig unzureichend), aber ich schlage vor, einen etwas anderen Weg einzuschlagen. Übrigens, wenn wir nicht 170 Schritte im Intervall machen, sondern 128 (ich sehe keinen Grund, uns von diesem Schritt abzuhalten), dann würde diese Idee perfekt zu uns passen. Wenn wir die Tatsache berücksichtigen, dass die Konstanten, die die KB definieren, durch Ganzzahlen gegeben sind und der einzige Parameter T durch einen Bruchteil der Form dargestellt werden kann und / und wir das Ergebnis zum Rendern auf dem Bildschirm verwenden, dh in Ganzzahlkoordinaten übersetzen, können wir Mach einfach alles in ganzen Zahlen, die viel schneller ablaufen.
Wir verwenden nur die letzte Formel und schreiben sie in der neuen Notation neu
(=> 2 * 2 + 2 /), wobei A1 und B1 auf die gleiche Weise wie für PT berechnet werden. Offensichtlich sind alle Zahlen ganze Zahlen und entsprechende Operationen sollten viel schneller ausgeführt werden. Um die Genauigkeit während der Operation der ganzzahligen Division (2/3 = 1! = 1,5) nicht zu verlieren und die Division im allerletzten Moment durchzuführen, transformieren wir die Formel leicht in die Form
(=> 4 * 2 + 2 /). Alle FT-Zahlen, also implementieren wir diesen Algorithmus und erhalten ... hier sind Sie, Großmutter und Yuryevs Tag ... 1869 Zyklen, aber das ist viel schlimmer als für FT, wir haben damit angefangen, eine Art Müll, weil ganze Zahlen viel schneller sind.
Wir beginnen mit der Nachbesprechung und es stellt sich heraus, dass es nicht ausreicht, nur die Art der Variablen zu ändern. Erstens müssen wir Zahlen verwenden, die nicht 8 oder sogar 16, sondern 32 Bit sind, da sonst ein Überlauf auftritt und lange Zahlen zwar schneller als PT, aber nicht so sehr, dass die Fehler im Algorithmus ausgeglichen werden. Zweitens sind diese Fehler vorhanden Wir hatten wieder Konstanten für jedes Maß berechnet - wir entfernen sie durch vorläufige Berechnung B2 = B1 * I, A2 = A * I * I. Dann bekommen wir
(=> 2 * 2 + 2 /) mit einem Ergebnis von 1684 ist besser als das vorherige, aber wir sind trotzdem nicht davon weggekommen.
Wir schließen die Berechnung einer weiteren Konstanten aus And2 = And * Und wir bekommen
(=> 2 * 2 + 1 /), mit einer Ausführungszeit von 956 Zyklen - aber das ist interessant, der Ausschluss einer Operation führte zu einer signifikanten Steigerung der Produktivität.
Das verlangsamt uns - die Teilung, weil es eine sehr zeitaufwändige Operation ist, aber wir haben einen interessanten Trick, um damit umzugehen. Um den Ausdruck 1 / zu berechnen, können wir Elementartransformationen durchführen 1 / = 1 / * ( / ) = 1 * ( / ) / . Wenn wir den Grad zwei als H wählen, kann die Division durch H durch Verschiebungen ersetzt werden, und wenn der Exponent ein Vielfaches von 8 ist, werden selbst Verschiebungen nicht benötigt. Und der Wert von N / A muss ehrlich berechnet werden, aber nur einmal, wonach nur noch die Multiplikation im Berechnungszyklus verbleibt.
Beachten Sie die Tatsache, dass wir eine nicht ganz korrekte Konvertierung durchgeführt und die N / A durch ihren gerundeten Wert K ersetzt haben, um zu Operationen ausschließlich mit ganzen Zahlen überzugehen. Die Unrichtigkeit besteht im Verlust der Genauigkeit, und es sollten zusätzliche Untersuchungen durchgeführt werden, um die Anwendbarkeit dieses Ansatzes auf unseren Fall zu beweisen. Wir schreiben H / I in der Form (K * I + d) / I = K + (d / I), wobei q kleiner als I ist. Dann ist der absolute Fehler beim Gehen zu H / I nach K d / I und der relative Fehler ist d / I. I / (K + d / I)> = d / I / (K + 1) ~ d / I / K, vorausgesetzt, K >> 1 (dies ist keine Verschiebung). Daraus folgt, dass der Wert von H so groß wie möglich gewählt werden sollte, da der absolute Berechnungsfehler gleich A * d / I / K> = A * 1 / N / I ist. Wenn wir wollen, dass der Fehler nicht mehr als eins ist, müssen wir der Bedingung A / K <= 1 standhalten, dann K> = A, K * I> = A * I konvertieren, was H> = A * I bedeutet, dann tun wir es nicht an Genauigkeit verlieren. In unserem Fall A <= 256 und I <= 256 erhalten wir H> = 2 ** 16, was durchaus akzeptabel ist. Offensichtlich sollten in den obigen Formeln die Module der ursprünglichen Nummern verwendet werden.
Wir stellen für die Zukunft fest, dass, wenn wir nicht abrunden, sondern auf die nächste ganze Zahl zugehen, die Anforderungen etwas reduziert sind und H halb so viel sein sollte, obwohl es Nuancen gibt.
In jedem Fall können wir die erforderliche Genauigkeit bereitstellen und den folgenden Algorithmus erhalten: H = 2 ** 16; K = [N / A] (I <256); 0 <= und <= AND;
(=> 4 * 2 + 2 >> 16) wobei alle Operationen mit langen ganzen Zahlen ausgeführt werden. Wir implementieren diesen Algorithmus und erhalten 583 Taktzyklen ... aber dies ist bereits nahezu ideal, aber noch nicht ideal.
Als nächstes kommen die kleinen Einstellungen für ein bestimmtes MK - die Arbeit mit globalen Variablen ist schneller. als bei lokalen, aber noch schneller bei lokalen Registern, was zu einer Verkürzung der Zeit auf 506 Taktzyklen führt.
Ferner stellen wir fest, dass die letzte Multiplikation vor der Verschiebung mit 16-Bit-Zahlen durchgeführt werden kann, was 504 ergibt - eine Kleinigkeit, aber nett.
Insgesamt haben wir die Berechnungen im Vergleich zur „Stirn“ -Implementierung 1900/504 beschleunigt - mehr als dreimal, und wir haben überhaupt nicht genau das Wort verloren. Dies ist das Ergebnis, das ich als Zeitoptimierung bezeichne und nicht zu 20% im ursprünglichen Beitrag erhalten habe.
Ist es möglich, noch bessere Indikatoren zu erzielen - es ist möglich, aber dies ist das Thema des nächsten Beitrags.